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

zbMATH Keywords

NP-hardinteger linear programsminimisation

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(2)

• New class of 0-1 integer programs with tight approximation via linear relaxations
• Parametric nonlinear integer programming: The right-hand side case

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)