LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
复制标题
一些 NP 难问题的 LP 松弛与任何 LP 一样困难
DOI：
10.5555/3039686.3039775
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Tomáš Werner
中科院分区：
文献类型：
--
作者：
D. Prusa;Tomáš Werner
我们发现，解决线性规划（LP）松弛的许多经典的NP难组合优化问题是解决一般的LP问题一样困难。准确地说，一般的LP可以在线性时间内减少到这些问题中的每一个的LP松弛。这一结果对设计求解LP松弛的有效算法造成了根本性的限制，因为找到这样的算法可能会提高一般LP的最佳已知算法的复杂性。除了线性时间的减少，我们认为所考虑的问题的LP松弛下的对数空间减少是P-完全的，因此也很难并行化。
We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is as hard as solving the general LP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation of each of these problems. This result poses a fundamental limitation for designing efficient algorithms to solve the LP relaxations, because finding such an algorithm might improve the complexity of best known algorithms for the general LP. Besides linear-time reductions, we show that the LP relaxations of the considered problems are P-complete under log-space reduction, therefore also hard to parallelize.