A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
Fred J. Rispoli, Steven Cosares · SIAM Journal on Discrete Mathematics · 1998
We investigate the diameter of the polytope arising in the n-city symmetric traveling salesman problem (TSP) and perfect matching polytopes. Grötschel and Padberg [The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Intersci. Ser. Discrete Math., E. Lawler et al., eds., John Wiley, Chichester, 1985, pp. 251--305] conjectured that the diameter of the symmetric TSP polytope is 2, independent of n. We constructively show that its diameter is at most 4, for all $n \geq 3$. Our result also shows that the diameter of the perfect 2-matching polytope is at most 6, for every $n \geq 3$.