Thresholded covering algorithms for robust and max-min optimization
From MaRDI portal
Publication:403674
DOI10.1007/s10107-013-0705-5zbMath1297.05188OpenAlexW1975162826MaRDI QIDQ403674
Anupam Gupta, R. Ravi, Viswanath Nagarajan
Publication date: 29 August 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-013-0705-5
Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (7)
Approximation algorithms for stochastic combinatorial optimization problems ⋮ LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization ⋮ Universal Algorithms for Clustering Problems ⋮ Robust strategic planning for mobile medical units with steerable and unsteerable demands ⋮ On the power of static assignment policies for robust facility location problems ⋮ Exploiting the Structure of Two-Stage Robust Optimization Models with Exponential Scenarios ⋮ On the Optimality of Affine Policies for Budgeted Uncertainty Sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- A note on maximizing a submodular set function subject to a knapsack constraint
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Two-stage robust network design with exponential scenarios
- Tractable approximations to robust conic optimization problems
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Robust Convex Optimization
- An improved LP-based approximation for steiner tree
- Price of Correlations in Stochastic Optimization
- A general approach to online network optimization problems
- Theory and Applications of Robust Optimization
- Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- An approximation scheme for stochastic linear programming and its application to stochastic integer programs
- The Online Set Cover Problem
- The all-or-nothing multicommodity flow problem
- Multicommodity flow, well-linked terminals, and routing problems
- Saving an epsilon
- Approximating the k-multicut problem
- Dynamic Steiner Tree Problem
- An analysis of approximations for maximizing submodular set functions—I
- Randomized metarounding
- Approximation algorithms for partial covering problems
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
- Robust Combinatorial Optimization with Exponential Scenarios
- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Thresholded covering algorithms for robust and max-min optimization
