TY - JOUR

T1 - Robust and maxmin optimization under matroid and knapsack uncertainty sets

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Ravi, R.

N1 - Publisher Copyright:
© 2015 ACM.

PY - 2015/11

Y1 - 2015/11

N2 - Consider the following problem: given a set system (U, Omega;) and an edge-weighted graph G = (U, E) on the same universe U, find the set A ∈ Ω such that the Steiner tree cost with terminals A is as large as possible-"which set in Omega; is the most difficult to connect up?" This is an example of a max-min problem: find the set A ∈ Ω such that the value of some minimization (covering) problem is as large as possible. In this article, we show that for certain covering problems that admit good deterministic online algorithms, we can give good algorithms for max-min optimization when the set system Ω is given by a p-system or knapsack constraints or both. This result is similar to results for constrained maximization of submodular functions. Although many natural covering problems are not even approximately submodular, we show that one can use properties of the online algorithm as a surrogate for submodularity Moreover, we give stronger connections between max-min optimization and two-stage robust optimization, and hence give improved algorithms for robust versions of various covering problems, for cases where the uncertainty sets are given by p-systems and knapsack constraints.

AB - Consider the following problem: given a set system (U, Omega;) and an edge-weighted graph G = (U, E) on the same universe U, find the set A ∈ Ω such that the Steiner tree cost with terminals A is as large as possible-"which set in Omega; is the most difficult to connect up?" This is an example of a max-min problem: find the set A ∈ Ω such that the value of some minimization (covering) problem is as large as possible. In this article, we show that for certain covering problems that admit good deterministic online algorithms, we can give good algorithms for max-min optimization when the set system Ω is given by a p-system or knapsack constraints or both. This result is similar to results for constrained maximization of submodular functions. Although many natural covering problems are not even approximately submodular, we show that one can use properties of the online algorithm as a surrogate for submodularity Moreover, we give stronger connections between max-min optimization and two-stage robust optimization, and hence give improved algorithms for robust versions of various covering problems, for cases where the uncertainty sets are given by p-systems and knapsack constraints.

KW - Approximation algorithms

KW - Online algorithms

KW - Robust optimization

KW - Submodularity

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

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

U2 - 10.1145/2746226

DO - 10.1145/2746226

M3 - Article

AN - SCOPUS:84947923518

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 10

ER -