TY - GEN

T1 - Thrifty algorithms for multistage robust optimization

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Vazirani, Vijay V.

PY - 2013

Y1 - 2013

N2 - We consider a class of multi-stage robust covering problems, where additional information is revealed about the problem instance in each stage, but the cost of taking actions increases. The dilemma for the decision-maker is whether to wait for additional information and risk the inflation, or to take early actions to hedge against rising costs. We study the "k-robust" uncertainty model: in each stage i = 0, 1,..., T, the algorithm is shown some subset of size ki that completely contains the eventual demands to be covered; here k1 > k2 > ⋯ > kT which ensures increasing information over time. The goal is to minimize the cost incurred in the worst-case possible sequence of revelations. For the multistage k-robust set cover problem, we give an O(logm + log n)-approximation algorithm, nearly matching the Ω(log n + log m/log log m) hardness of approximation [4] even for T = 2 stages. Moreover, our algorithm has a useful "thrifty" property: it takes actions on just two stages. We show similar thrifty algorithms for multi-stage k-robust Steiner tree, Steiner forest, and minimum-cut. For these problems our approximation guarantees are O(min{ T, log n, log λmax}), where λmax is the maximum inflation over all the stages. We conjecture that these problems also admit O(1)-approximate thrifty algorithms.

AB - We consider a class of multi-stage robust covering problems, where additional information is revealed about the problem instance in each stage, but the cost of taking actions increases. The dilemma for the decision-maker is whether to wait for additional information and risk the inflation, or to take early actions to hedge against rising costs. We study the "k-robust" uncertainty model: in each stage i = 0, 1,..., T, the algorithm is shown some subset of size ki that completely contains the eventual demands to be covered; here k1 > k2 > ⋯ > kT which ensures increasing information over time. The goal is to minimize the cost incurred in the worst-case possible sequence of revelations. For the multistage k-robust set cover problem, we give an O(logm + log n)-approximation algorithm, nearly matching the Ω(log n + log m/log log m) hardness of approximation [4] even for T = 2 stages. Moreover, our algorithm has a useful "thrifty" property: it takes actions on just two stages. We show similar thrifty algorithms for multi-stage k-robust Steiner tree, Steiner forest, and minimum-cut. For these problems our approximation guarantees are O(min{ T, log n, log λmax}), where λmax is the maximum inflation over all the stages. We conjecture that these problems also admit O(1)-approximate thrifty algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84875546179&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875546179&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36694-9_19

DO - 10.1007/978-3-642-36694-9_19

M3 - Conference contribution

AN - SCOPUS:84875546179

SN - 9783642366932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 217

EP - 228

BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings

T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

Y2 - 18 March 2013 through 20 March 2013

ER -