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

DOI10.1016/j.dam.2011.01.026zbMath1228.90103OpenAlexW2116501956MaRDI QIDQ643021

Etienne de Klerk, Cristian Dobre

Publication date: 27 October 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.01.026

zbMATH Keywords

semidefinite programmingtraveling salesman problemcirculant matrices

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals ⋮ Special Frequency Quadrilaterals and an Application ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem

Uses Software

• SeDuMi
• YALMIP
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Efficiently solvable special cases of bottleneck travelling salesman problems
• On hamiltonian Toeplitz graphs
• Hamiltonian cycles in circulant digraphs with two stripes
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solution of a Large-Scale Traveling-Salesman Problem
• The Travelling Salesman Problem in symmetric circulant matrices with two stripes
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Combinatorial optimization. Theory and algorithms.