### Abstract

Original language | English |
---|---|

Pages (from-to) | 1815-1826 |

Journal | Discrete Applied Mathematics |

Volume | 159 |

Issue number | 16 |

DOIs | |

Publication status | Published - 2011 |

### Fingerprint

### Keywords

- semidefinite programming
- traveling salesman problem
- circulant matrices

### Cite this

}

*Discrete Applied Mathematics*, vol. 159, no. 16, pp. 1815-1826. https://doi.org/10.1016/j.dam.2011.01.026

**A comparison of lower bounds for the symmetric circulant traveling salesman problem.** / de Klerk, E.; Dobre, C.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - A comparison of lower bounds for the symmetric circulant traveling salesman problem

AU - de Klerk, E.

AU - Dobre, C.

PY - 2011

Y1 - 2011

N2 - 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, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559–1573]. 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, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138–1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].

AB - 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, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559–1573]. 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, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138–1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].

KW - semidefinite programming

KW - traveling salesman problem

KW - circulant matrices

U2 - 10.1016/j.dam.2011.01.026

DO - 10.1016/j.dam.2011.01.026

M3 - Article

VL - 159

SP - 1815

EP - 1826

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 16

ER -