On Semidefinite Programming Relaxations of the Traveling Salesman Problem
From MaRDI portal
Publication:3648520
DOI10.1137/070711141zbMath1196.90094arXiv0902.1843WikidataQ56874368 ScholiaQ56874368MaRDI QIDQ3648520
Renata Sotirov, Etienne de Klerk, Dimitrii V. Pasechnik
Publication date: 27 November 2009
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0902.1843
Related Items
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, 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, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, A polynomial time constraint-reduced algorithm for semidefinite optimization problems, 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, Exploiting special structure in semidefinite programming: a survey of theory and applications, 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, The symmetric quadratic traveling salesman 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, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives