A Comparison of Lower Bounds for the Symmetric Circulant Traveling Salesman Problem

Etienne De Klerk(e.deklerkuvt.nl)
Cristian Dobre(c.dobreuvt.nl)

Abstract: When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, and R. Sotirov. On semidefinite programming relaxation of the traveling salesman problem, Siam Journal Optimization}, 19:4, 1559--1573, 2008]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held and R.M. Karp. The traveling salesman problem and minimum spanning trees. Operations Research, 18:1138-1162, 1970], the 1-tree bound, and the closed-form bound for SCTSP proposed in [Van der Veen, J.A.A. Solvable cases of TSP with various objective functions, PhD thesis, Groningen University, 1992].

Keywords: semidefinite programming, traveling salesman problem, circulant matrices

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Working paper, CentER, Tilburg University, 2008.

Download: [PDF]

Entry Submitted: 09/09/2009
Entry Accepted: 09/10/2009
Entry Last Modified: 09/09/2009

Modify/Update this entry