On linear characterizations of combinatorial optimization problems
On linear characterizations of combinatorial optimization problems
复制标题
组合优化问题的线性表征
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou
中科院分区：
文献类型：
--
作者：
R. Karp;C. Papadimitriou
我们证明，除非NP=co-NP--一个非常不可能发生的事件，否则不可能存在与任何NP-完全组合优化问题相关的多面体的线性不等式的易于计算的描述。我们还应用线性规划的椭球法证明了一个组合优化问题在多项式时间内可解的充要条件是它允许一个违反不等式的小生成元。
We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP -- a very unlikely event. We also apply the ellipsoid method for linear programming to show that a combinatorial optimization problem is solvable in polynomial time if and only if it admits a small generator of violated inequalities.