Speakers:  Sylvia Boyd and Genevieve Labonte
Time:      Tuesday Sep 25 14:30
Place:     MCD 318 (MacDonald Hall), SITE, University of Ottawa
Title:     Finding the exact integrality gap for small 
           Travelling Salesman Problems

Abstract:
The Symmetric Travelling Salesman Problem is to find a minimum cost 
Hamiltonian cycle in the weighted complete graph on n nodes.  This problem
is well known to be NP-hard even in the metric case, and thus it is
considered highly unlikely that an efficient algorithm will ever be found
for solving it.

One direction which seems promising for obtaining improved STSP solutions
is the study of a linear relaxation of the STSP called the Subtour
Elimination Problem (SEP).  A long standing conjecture in combinatorial
optimization says that the integrality gap of the SEP (i.e. the worst
possible ratio of the STSP optimum to the SEP optimum) is 4/3 in the
metric case.  Note that a proof of this conjecture would give a 4/3
approximation for the STSP and an algorithmic proof would lead to a 4/3
approximation algorithm for the STSP.  Currently the best upper bound
known for this integrality gap is 3/2, and the best approximation
algorithm known for the metric STSP is the 3/2 Christofides algorithm.

Finding the exact value for the integrality gap for the SEP is difficult
even for small values of n due to the exponential size of the data
involved.  In this talk we describe how we were able to overcome such
problems and obtain the exact integrality gap for all value of n up to 10.
Our results give a verification of the 4/3 conjecture for small values of
n, and also give rise to a new stronger form of the conjecture which is
dependent on n.