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