On Semidefinite Programming Relaxations of the Traveling Salesman Problem
From MaRDI portal
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 the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proc. 7th Int. IPCO Conference, Springer, London, 1999, pp. 126--136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
Recommendations
- scientific article; zbMATH DE number 1873286
- Solving a semidefinite relaxation of the traveling salesman problem.
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- scientific article; zbMATH DE number 1342125
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
Cited in
(33)- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Solving a semidefinite relaxation of the traveling salesman problem.
- Relaxed tours and path ejections for the traveling salesman problem
- The demand weighted vehicle routing problem
- A primal barrier function phase I algorithm for nonsymmetric conic optimization problems
- Gaddum's test for symmetric cones
- Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP
- Exploiting symmetry in copositive programs via semidefinite hierarchies
- A positive semidefinite approximation of the symmetric traveling salesman polytope
- Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables
- The symmetric quadratic traveling salesman problem
- Minimum energy configurations on a toric lattice as a quadratic assignment problem
- Relaxations of combinatorial problems via association schemes
- Invariant Semidefinite Programs
- SDP relaxations for some combinatorial optimization problems
- An improved interior-point cutting-plane method for binary quadratic optimization
- On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
- On solving the quadratic shortest path problem
- A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives
- scientific article; zbMATH DE number 1342125 (Why is no real title available?)
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- scientific article; zbMATH DE number 2159169 (Why is no real title available?)
- scientific article; zbMATH DE number 1873286 (Why is no real title available?)
- A polynomial time constraint-reduced algorithm for semidefinite optimization problems
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- Hidden Hamiltonian cycle recovery via linear programming
- Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
- On semidefinite programming bounds for graph bandwidth
- On Integrality in Semidefinite Programming for Discrete Optimization
- A comparison of lower bounds for the symmetric circulant traveling salesman problem
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- A semidefinite optimization approach to the target visitation problem
This page was built for publication: On Semidefinite Programming Relaxations of the Traveling Salesman Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3648520)
