Summary: Following the well-studied two-stage optimization framework for stochastic optimization, we study approximation algorithms for robust two-stage optimization problems with an exponential number of scenarios. Prior to this work, K. Dhamdhere, V. Goyal, R. Ravi and M. Singh [“How to pay, come what may: approximation algorithms for demand-robust covering problems”, in: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS’05, 367–378 (2005)] introduced approximation algorithms for two-stage robust optimization problems with explicitly given scenarios. In this paper, we assume the set of possible scenarios is given implicitly, for example by an upper bound on the number of active clients. In two-stage robust optimization, we need to pre-purchase some resources in the first stage before the adversary’s action. In the second stage, after the adversary chooses the clients that need to be covered, we need to complement our solution by purchasing additional resources at an inflated price. The goal is to minimize the cost in the worst-case scenario. We give a general approach for solving such problems using LP rounding. Our approach uncovers an interesting connection between robust optimization and online competitive algorithms. We use this approach, together with known online algorithms, to develop approximation algorithms for several robust covering problems, such as set cover, vertex cover, and edge cover. We also study a simple buy-at-once algorithm that either covers all items in the first stage or does nothing in the first stage and waits to build the complete solution in the second stage. We show that this algorithm gives tight approximation factors for unweighted variants of these covering problems, but performs poorly for general weighted problems.
For the entire collection see [Zbl 1121.90003].