Thresholded covering algorithms for robust and max-min optimization

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

zbMATH Keywords

\(k\)-robust modeltwo-stage robust covering problem

Mathematics Subject Classification ID

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

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
• 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
• Dial a Ride from k -forest
• 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