Approximating integer programs with positive right-hand sides

DOI10.1016/j.ipl.2010.02.011zbMath1229.90098OpenAlexW2027280132MaRDI QIDQ656570

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

zbMATH Keywords

NP-hardinteger linear programsminimisation

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• On the hardness of approximating minimum vertex cover
• A fast approximation algorithm for the multicovering problem
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Rounding algorithms for covering problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• Approximability of Sparse Integer Programs
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the Greedy Heuristic for Continuous Covering and Packing Problems
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• The complexity of satisfiability problems

This page was built for publication: Approximating integer programs with positive right-hand sides