LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

DOI10.1137/1.9781611974782.89zbMath1410.68148OpenAlexW4248646072MaRDI QIDQ4575832

Tomáš Werner, Daniel Průša

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)

Related Items (2)

Classes of linear programs solvable by coordinate-wise minimization ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program

This page was built for publication: LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP