Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
From MaRDI portal
Abstract: 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.
Recommendations
- Robust combinatorial optimization with knapsack uncertainty
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- Restricted robust uniform matroid maximization under interval uncertainty
- Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
- Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
- Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty
- On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Min-max-min robust combinatorial optimization
- scientific article; zbMATH DE number 6914444
Cited in
(15)- On the power of static assignment policies for robust facility location problems
- A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Constrained submodular maximization via greedy local search
- Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
- Thresholded covering algorithms for robust and max-min optimization
- On the optimality of affine policies for budgeted uncertainty sets
- A polynomial-time approximation scheme for sequential batch testing of series systems
- Independent sets and vertex covers considered within the context of robust optimization
- Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
- Universal Algorithms for Clustering Problems
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Robust algorithms for TSP and Steiner tree
- Adaptive-adversary-robust algorithms via small copy tree embeddings
- Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty
This page was built for publication: Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962207)
