Robust and maxmin optimization under matroid and knapsack uncertainty sets

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number10
JournalACM Transactions on Algorithms
Issue number1
StatePublished - Nov 2015


  • Approximation algorithms
  • Online algorithms
  • Robust optimization
  • Submodularity

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Robust and maxmin optimization under matroid and knapsack uncertainty sets'. Together they form a unique fingerprint.

Cite this