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

DOI10.1137/1.9781611974782.89zbMATH Open1410.68148OpenAlexW4248646072MaRDI QIDQ4575832FDOQ4575832

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• 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
• Principles and Practice of Constraint Programming – CP 2004

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)