On linear characterizations of combinatorial optimization problems
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Solution to the traveling salesman problem using heuristic function maximizationJournal of Guidance, Control, and Dynamics, 1988
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- On the symmetric travelling salesman problem II: Lifting theorems and facetsMathematical Programming, 1979
- On the symmetric travelling salesman problem I: InequalitiesMathematical Programming, 1979
- Bounds on positive integral solutions of linear Diophantine equationsProceedings of the American Mathematical Society, 1976
- Properties of vertex packing and independence system polyhedraMathematical Programming, 1974
- On the facial structure of set packing polyhedraMathematical Programming, 1973
- Edmonds polytopes and weakly hamiltonian graphsMathematical Programming, 1973
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965
- Solution of a Large-Scale Traveling-Salesman ProblemJournal of the Operations Research Society of America, 1954