Rounding algorithms for covering problems
From MaRDI portal
Publication:1380937
DOI10.1007/BF01582131zbMATH Open0894.90121DBLPjournals/mp/BertsimasV98WikidataQ100884359 ScholiaQ100884359MaRDI QIDQ1380937FDOQ1380937
Authors: Dimitris Bertsimas, Rakesh V. Vohra 
Publication date: 11 March 1998
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Integer programming (90C10) Discrete location and assignment (90B80)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Optimization, approximation, and complexity classes
- A fast approximation algorithm for the multicovering problem
- On the ratio of optimal integral and fractional covers
- Title not available (Why is that?)
- Title not available (Why is that?)
- A linear-time approximation algorithm for the weighted vertex cover problem
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Heuristics for the fixed cost median problem
- A Selection Problem of Shared Fixed Costs and Network Flows
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Title not available (Why is that?)
- A primal-dual approximation algorithm for generalized Steiner network problems
- A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (26)
- Approximating covering integer programs with multiplicity constraints
- LP based heuristics for the multiple knapsack problem with assignment restrictions
- On the number and arrangement of sensors for the multiple covering of bounded plane domains
- Geometric rounding: A dependent randomized rounding scheme
- Experimental and Efficient Algorithms
- The controlled rounding problem: Complexity and computational experience
- Optimization of the number and arrangement of circles of two radii for forming a \(k\)-covering of a bounded set
- Rounding to an integral program
- New approaches to covering and packing problems
- On dependent randomized rounding algorithms
- Randomized rounding for routing and covering problems: experiments and improvements
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Minimizing average project team size given multi-skilled workers with heterogeneous skill levels
- Approximation algorithms for integer covering problems via greedy column generation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Approximability of open \(k\)-monopoly problems
- A branch-and-cut algorithm for the pallet loading problem
- The archievable region method in the optimal control of queueing systems; formulations, bounds and policies
- Approximation of optima of integer programs of the packing—covering type
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Approximating integer programs with positive right-hand sides
- Distributed algorithms for covering, packing and maximum weighted matching
- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
- The set covering problem revisited: an empirical study of the value of dual information
This page was built for publication: Rounding algorithms for covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380937)
