Thresholded covering algorithms for robust and max-min optimization
From MaRDI portal
Publication:403674
DOI10.1007/S10107-013-0705-5zbMATH Open1297.05188OpenAlexW1975162826MaRDI QIDQ403674FDOQ403674
Authors: Anupam Gupta, Viswanath Nagarajan, R. Ravi 
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
Recommendations
- Thresholded Covering Algorithms for Robust and Max-min Optimization
- Formulation and algorithms for the robust maximal covering location problem
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- On minquantile and maxcovering optimisation
- Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
- Robust min-max regret covering problems
- Thresholding algorithms, maxisets and well-concentrated bases
- Thrifty algorithms for multistage robust optimization
- Min-max-min robust combinatorial optimization
- Adaptive thresholding technique for solving optimization problems on attainable sets of \((\max,\min)\)-linear systems.
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
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Theory and applications of robust optimization
- 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
- Title not available (Why is that?)
- 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
- Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions (extended abstract)
- Robust Combinatorial Optimization with Exponential Scenarios
- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
- Title not available (Why is that?)
- Improved performance of the greedy algorithm for partial cover
- Title not available (Why is that?)
- 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: a 2-approximation for the \(k\)-MST problem in graphs
- 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
- Title not available (Why is that?)
- Randomized metarounding
Cited In (16)
- Robust multicovers: algorithms and complexity
- Robust strategic planning for mobile medical units with steerable and unsteerable demands
- Approximation algorithms for stochastic combinatorial optimization problems
- Robust multicovers with budgeted uncertainty
- Robust Combinatorial Optimization with Exponential Scenarios
- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
- Thrifty algorithms for multistage robust optimization
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Universal Algorithms for Clustering Problems
- Maxisets for \(\mu \) -thresholding rules
- Two-stage robust network design with exponential scenarios
- On the optimality of affine policies for budgeted uncertainty sets
- 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
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)
