94-12 A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope

DIMACS TR: 94-12

A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope

Authors: Fred J. Rispoli, Steven Cosares

ABSTRACT
A conjecture of Grotschel and Padbrg 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 appearing in the literature is [n/2]. This paper gives a constructive proof showing that for every pair of tours having a perfect matching in common, the distance between their corresponding extreme points is at most 2. Moreover, the diameter of the symmetric TSP polytope is at most 4, independent of n. A new and simpler proof is also given demon- strating that the diameter of the perfect matching polytope is 2, a fact estblished by Padberg and Rao.

Paper only.

DIMACS Home Page