Rounding algorithms for covering problems

DOI10.1007/BF01582131zbMath0894.90121DBLPjournals/mp/BertsimasV98WikidataQ100884359 ScholiaQ100884359MaRDI QIDQ1380937

Rakesh V. Vohra, Dimitris J. Bertsimas

Publication date: 11 March 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

heuristicsapproximationrounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (15)

Minimizing average project team size given multi-skilled workers with heterogeneous skill levels ⋮ LP based heuristics for the multiple knapsack problem with assignment restrictions ⋮ The archievable region method in the optimal control of queueing systems; formulations, bounds and policies ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Approximating integer programs with positive right-hand sides ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ The set covering problem revisited: an empirical study of the value of dual information ⋮ Approximability of open \(k\)-monopoly problems ⋮ On the Number and Arrangement of Sensors for the Multiple Covering of Bounded Plane Domains ⋮ Optimization of the number and arrangement of circles of two radii for forming a \(k\)-covering of a bounded set ⋮ On dependent randomized rounding algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast approximation algorithm for the multicovering problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Heuristics for the fixed cost median problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the hardness of approximating minimization problems
• On the Greedy Heuristic for Continuous Covering and Packing Problems
• A primal-dual approximation algorithm for generalized Steiner network problems
• A Selection Problem of Shared Fixed Costs and Network Flows

This page was built for publication: Rounding algorithms for covering problems