Etienne de Klerk (Tilburg University, The Netherlands)

On semidefinite programming relaxations of the travelling salesman problem
Joint work with Renata Sotirov and Dima Pasechnik.
Wednesday 8 October 2008 at 15.30, JCMB 6206

Abstract

We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates one by Cvetkovic et al.

Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.

The new relaxation has an interpretation in terms of the association scheme generated by the optimal tour.

Seminars by year

Current 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996