## 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