Two-stage Robust Network Design with Exponential Scenarios
We study two-stage robust variants of combinatorial optimization problems on undirected graphs, like Steiner tree, Steiner forest, and uncapacitated facility location. Robust optimization problems, previously studied by Dhamdhere etal. (Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS05), pp.367378, 2005), Golovin etal. (Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006), and Feige etal. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp.439453, 2007), are two-stage planning problems in which the requirements are revealed after some decisions are taken in Stage1. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust k-Steiner tree problem, for example, one buys some edges in Stage 1. Then k terminals are revealed in Stage 2 and one has to buy more edges, at a higher cost, to complete the Stage 1 solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario.
robust network design approximation algorithms hardness of approximation robust steiner tree robust steiner forest robust facility location