Approximating covering integer programs with multiplicity constraints
- 1 August 2003
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 129 (2-3) , 461-473
- https://doi.org/10.1016/s0166-218x(02)00598-x
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Approximation Algorithms for Single-Source Unsplittable FlowSIAM Journal on Computing, 2001
- A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global CriteriaSIAM Journal on Computing, 2001
- Approximating low-congestion routing and column-restricted packing problemsInformation Processing Letters, 2000
- Improved Approximation Guarantees for Packing and Covering Integer ProgramsSIAM Journal on Computing, 1999
- Rounding algorithms for covering problemsMathematical Programming, 1998
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- On the Greedy Heuristic for Continuous Covering and Packing ProblemsSIAM Journal on Algebraic Discrete Methods, 1982
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975