On semidefinite programming relaxations of the traveling salesman problem

Simple item page
dc.creatorde Klerk, Etienne
dc.creatorPasechnik, Dmitrii V.
dc.creatorSotirov, Renata
dc.date2009-02-11
dc.date.accessioned2026-07-07T12:40:33Z
dc.date.available2026-07-07T12:40:33Z
dc.descriptionWe 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.
dc.description18 pages, 1 figure (corrects the figure in the published version), LaTeX, MetaPost for the figure
dc.identifierhttps://arxiv.org/abs/0902.1843
dc.identifierhttp://arxiv.org/abs/0902.1843
dc.identifierSIAM J. Optim. Volume 19, Issue 4, pp. 1559-1573 (2008)
dc.identifierdoi:10.1137/070711141
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219474
dc.subjectOptimization and Control
dc.subjectCombinatorics
dc.subject90C22; 90C35
dc.titleOn semidefinite programming relaxations of the traveling salesman problem
dc.typetext

Files

Collections

arXiv