Approximating integer programs with positive right-hand sides
DOI10.1016/J.IPL.2010.02.011zbMATH Open1229.90098OpenAlexW2027280132MaRDI QIDQ656570FDOQ656570
Authors: Peter Jonsson, Johan Thapper 
Publication date: 18 January 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.011
Recommendations
- Approximability of sparse integer programs
- Approximability of Sparse Integer Programs
- New class of 0-1 integer programs with tight approximation via linear relaxations
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Integer programming as a framework for optimization and approximability
Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Integer programming (90C10)
Cites Work
- A fast approximation algorithm for the multicovering problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Title not available (Why is that?)
- The complexity of satisfiability problems
- On the hardness of approximating minimum vertex cover
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Rounding algorithms for covering problems
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Approximability of Sparse Integer Programs
Cited In (2)
This page was built for publication: Approximating integer programs with positive right-hand sides
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q656570)
