LP relaxations of some NP-hard problems are as hard as any LP

DOI10.1137/1.9781611974782.89MaRDI QIDQ4575832zbMATH OpenOpenAlexFDO

Authors Daniel Průša, Tomáš Werner

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.89

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximating CSPs using LP relaxation

Cited in

(6)

• Principles and Practice of Constraint Programming – CP 2004
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• On the space complexity of linear programming with preprocessing
• On the complexity of a special basis problem in LP
• Classes of linear programs solvable by coordinate-wise minimization
• The complexity of linear programming in \((\gamma ,\kappa )\)-form

This page was built for publication: LP relaxations of some NP-hard problems are as hard as any LP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575832)