Algorithms and Complexity Seminar
Approximation Algorithms for Demand-Robust Covering Problems
Vineet Goyal (CMU, MIT)
Most optimization problems in real-life do not have accurate estimates of the problem parameters at the optimization phase. Stochastic and robust optimization models have been studied widely in the literature to address the uncertainty in problem parameters. Robust optimization approaches have traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic optimization problems.
We consider a general two-stage covering problem (with two stages of decision making) where the right hand side of the covering constraints (or the demand) is uncertain. For instance, consider a set cover problem where we are given a family of subsets but the set of elements that need to be covered are uncertain. In our model, the uncertainty is given by a list of scenarios where each scenario specifies a set of elements that must be covered if that scenario materializes and an inflation factor by which each set would become costlier in that scenario. We are required to construct a first stage solution and for each scenario a second-stage augmentation solution (bought at an inflated cost) such that together with the first stage solution, it covers all the elements in that scenario and the objective is to minimize the total worst case costs over all scenarios.
We prove a result about the structure of the first stage solution of near-optimal solutions and provide approximation algorithms for specific problems such as Steiner tree, min-cut, minimum multi-cut, vertex cover and facility location in this model. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting. We also develop a `guess-and-prune' algorithm where we `guess' the worst case second stage cost which allows us to `prune' away a set of scenarios which can be completely satisfied within this bound. We use this approach and a Gomory-Hu tree based charging argument to obtain a constant-approximation for the minimum cut problem in our model.
This is joint work with K. Dhamdhere, D. Golovin, R. Ravi and M. Singh.