TY - GEN

T1 - Two-stage robust network design with exponential scenarios

AU - Khandekar, Rohit

AU - Kortsarz, Guy

AU - Mirrokni, Vahab

AU - Salavatipour, Mohammad R.

PY - 2008

Y1 - 2008

N2 - We study two-stage robust variants of combinatorial optimization problems like Steiner tree, Steiner forest, and uncapacitated facility location. The robust optimization problems, previously studied by Dhamdhere et al. [1], Golovin et al. [6], and Feige et al. [4], are two-stage planning problems in which the requirements are revealed after some decisions are taken in stage one. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust Steiner tree problem, for example, one buys some edges in stage one after which some terminals are revealed. In the second stage, one has to buy more edges, at a higher cost, to complete the stage one solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario. In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for Steiner tree), or any subset of k terminal-pairs (for Steiner forest), or any subset of k clients (for facility location). We present the first constant-factor approximation algorithms for the robust Steiner tree and robust uncapacitated facility location problems. For the robust Steiner forest problem with uniform inflation, we present an O(logn)-approximation and show that the problem with two inflation factors is impossible to approximate within O(log1/2 - ε n) factor, for any constant ε > 0, unless NP has randomized quasi-polynomial time algorithms. Finally, we show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question by [1] and [6].

AB - We study two-stage robust variants of combinatorial optimization problems like Steiner tree, Steiner forest, and uncapacitated facility location. The robust optimization problems, previously studied by Dhamdhere et al. [1], Golovin et al. [6], and Feige et al. [4], are two-stage planning problems in which the requirements are revealed after some decisions are taken in stage one. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust Steiner tree problem, for example, one buys some edges in stage one after which some terminals are revealed. In the second stage, one has to buy more edges, at a higher cost, to complete the stage one solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario. In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for Steiner tree), or any subset of k terminal-pairs (for Steiner forest), or any subset of k clients (for facility location). We present the first constant-factor approximation algorithms for the robust Steiner tree and robust uncapacitated facility location problems. For the robust Steiner forest problem with uniform inflation, we present an O(logn)-approximation and show that the problem with two inflation factors is impossible to approximate within O(log1/2 - ε n) factor, for any constant ε > 0, unless NP has randomized quasi-polynomial time algorithms. Finally, we show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question by [1] and [6].

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

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

U2 - 10.1007/978-3-540-87744-8_49

DO - 10.1007/978-3-540-87744-8_49

M3 - Conference contribution

AN - SCOPUS:57749204300

SN - 3540877436

SN - 9783540877431

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

SP - 589

EP - 600

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -