A Comparison of Lower Bounds for the Symmetric Circulant Traveling Salesman Problem
Etienne De Klerk(e.deklerkuvt.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.
Entry Submitted: 09/09/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|