DIMACS TR: 93-85
On the Diameter of the Symmetric Traveling Salesman Polytope
Author: Fred Rispoli
ABSTRACT
A conjecture of Grotschel and Padberg states that the diameter of
the polytope arising in the n-city symmetric traveling salesman
problem is 2, independent of n. To date, the best bound on this
diameter is [n/2]. This paper gives a constructive proof showing that
the diameter is at most 6, independent of n. The approach exploits a
characterization of neighboring extreme points for the perfect
2-matching polytope. A new and very short proof is also given
demonstrating that the diameter of the perfect matching polytope is 2,
a fact established by Padberg and Rao.
--- THIS TECH REPORT NOT AVAILABLE ON LINE ---
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-85.ps
DIMACS Home Page