Worst-case comparison of valid inequalities for the TSP
- 1 July 1995
- journal article
- Published by Springer Science and Business Media LLC in Mathematical Programming
- Vol. 69 (1-3), 335-349
- https://doi.org/10.1007/bf01585563
Abstract
We consider most of the known classes of valid inequalities for the graphical travelling salesman polyhedron and compute the worst-case improvement resulting from their addition to the subtour polyhedron. For example, we show that the comb inequalities cannot improve the subtour bound by a factor greater than 10/9. The corresponding factor for the class of clique tree inequalities is 8/7, while it is 4/3 for the path configuration inequalities.Keywords
This publication has 25 references indexed in Scilit:
- Survivable networks, linear programming relaxations and the parsimonious propertyMathematical Programming, 1993
- The traveling salesman problem in graphs with some excluded minorsMathematical Programming, 1992
- Small Travelling Salesman PolytopesMathematics of Operations Research, 1991
- Optimizing over the subtour polytope of the travelling salesman problemMathematical Programming, 1990
- A new class of cutting planes for the symmetric travelling salesman problemMathematical Programming, 1988
- The traveling salesman problem on a graph and some related integer polyhedraMathematical Programming, 1985
- Solving Large-Scale Symmetric Travelling Salesman Problems to OptimalityManagement Science, 1980
- On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and FacetsMathematics of Operations Research, 1980
- On the symmetric travelling salesman problem: Solution of a 120-city problemPublished by Springer Science and Business Media LLC ,1980
- Edmonds polytopes and weakly hamiltonian graphsMathematical Programming, 1973