Name
Title | ||
|---|---|---|
How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems |
Abstract | ||
|---|---|---|
Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worstcase 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 propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and un-capacitated facility location. 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/SFCS.2005.42 | FOCS |
Keywords | Field | DocType |
minimal feasible solution,defining data,two-stage stochastic optimization problem,cut problem,demand-robust setting,demand-robust covering problems,minimum cut,optimization problem,approximation algorithms,robust optimization,first-stage solution,general structural lemma,steiner tree,objective function,computational complexity,stochastic programming,vertex cover,shortest path,facility location | Discrete mathematics,Approximation algorithm,Combinatorics,Stochastic optimization,Mathematical optimization,Robust optimization,Computer science,L-reduction,Combinatorial optimization,Stochastic programming,Optimization problem,Covering problems | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-2468-0 | 36 |
PageRank | References | Authors |
1.26 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kedar Dhamdhere | 1 | 351 | 20.83 |
| Vineet Goyal | 2 | 156 | 10.88 |
| R. Ravi | 3 | 2898 | 275.40 |
| mohit singh | 4 | 515 | 38.42 |