Thresholded covering algorithms for robust and max-min optimization

DOI10.1007/S10107-013-0705-5zbMATH Open1297.05188OpenAlexW1975162826MaRDI QIDQ403674FDOQ403674

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

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A threshold of ln n for approximating set cover
• Theory and Applications of Robust Optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for partial covering problems
• A General Approximation Technique for Constrained Forest Problems
• A tight bound on approximating arbitrary metrics by tree metrics
• Robust convex optimization
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Dynamic Steiner Tree Problem
• Two-stage robust network design with exponential scenarios
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• An improved LP-based approximation for Steiner tree
• Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• The Online Set Cover Problem
• Robust Combinatorial Optimization with Exponential Scenarios
• Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
• Improved performance of the greedy algorithm for partial cover
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Tractable approximations to robust conic optimization problems
• Saving an epsilon
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• A general approach to online network optimization problems
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• A note on maximizing a submodular set function subject to a knapsack constraint
• Price of correlations in stochastic optimization
• Dial a Ride from k -forest
• The all-or-nothing multicommodity flow problem
• Multicommodity flow, well-linked terminals, and routing problems
• Approximating the k-multicut problem
• Randomized metarounding

Cited In (10)

• On the Optimality of Affine Policies for Budgeted Uncertainty Sets
• Robust strategic planning for mobile medical units with steerable and unsteerable demands
• Approximation algorithms for stochastic combinatorial optimization problems
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• Universal Algorithms for Clustering Problems
• Maxisets for \(\mu \) -thresholding rules
• On the power of static assignment policies for robust facility location problems
• Thresholded Covering Algorithms for Robust and Max-min Optimization
• Exploiting the Structure of Two-Stage Robust Optimization Models with Exponential Scenarios
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

Recommendations

• Thresholding algorithms, maxisets and well-concentrated bases 👍 👎
• Min-max-min robust combinatorial optimization 👍 👎
• Formulation and algorithms for the robust maximal covering location problem 👍 👎
• On minquantile and maxcovering optimisation 👍 👎
• Robust min-max regret covering problems 👍 👎
• Thresholded Covering Algorithms for Robust and Max-min Optimization 👍 👎
• Adaptive thresholding technique for solving optimization problems on attainable sets of (max, min)-linear systems 👍 👎
• Reoptimization of max \(k\)-cover: approximation ratio threshold 👍 👎
• Thrifty Algorithms for Multistage Robust Optimization 👍 👎
• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems 👍 👎

This page was built for publication: Thresholded covering algorithms for robust and max-min optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403674)