Computer Science – Data Structures and Algorithms
Scientific paper
2010-12-22
Computer Science
Data Structures and Algorithms
17 pages. Preliminary version combining this paper and http://arxiv.org/abs/0912.1045 appeared in ICALP 2010
Scientific paper
Consider the following problem: given a set system (U,I) and an edge-weighted graph G = (U, E) on the same universe U, find the set A in I such that the Steiner tree cost with terminals A is as large as possible: "which set in I is the most difficult to connect up?" This is an example of a max-min problem: find the set A in I such that the value of some minimization (covering) problem is as large as possible. In this paper, we show that for certain covering problems which admit good deterministic online algorithms, we can give good algorithms for max-min optimization when the set system I is given by a p-system or q-knapsacks 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 q-knapsacks.
Gupta Anupam
Nagarajan Viswanath
Ravi R.
No associations
LandOfFree
Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-582200