On Linear Characterizations of Combinatorial Optimization Problems

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.

Authors

• Richard M. Karp
• Christos H. Papadimitriou

Keywords

• Polynomials
• Computer science
• Laboratories
• Linear programming
• Optimization methods
• Ellipsoids
• Indexing
• Vectors
• Combinatorial Optimization Problem
• Combinatorial Problem
• Linear Inequalities
• NP-complete Problem
• Feasible Solution
• Hyperplane
• Linear Problem
• Feasible Set
• Case Method
• Extreme Points
• Problem Instances
• Polynomial-time Algorithm
• Point R
• Feasible Point
• Traveling Salesman Problem
• Convex Polytope
• Integer Vector
• Affine Space
• Satisfactory Description