Please use this identifier to cite or link to this item:
Title: On semidefinite programming relaxations of the traveling salesman problem
Authors: De Klerk, Etienne.
Pasechnik, Dmitrii V.
Sotirov, Renata.
Keywords: DRNTU::Science::Mathematics::Applied mathematics::Operational research
Issue Date: 2008
Source: De Klerk, E., Pasechnik, D. V., & Sotirov, R. (2008). On semidefinite programming relaxations of the traveling salesman problem. SIAM Journal on Optimization, 19(4), 1559–1573.
Series/Report no.: SIAM journal on optimization
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. Cvetković, M. Cangalović, and V. Kovačević-Vujčić, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, London, UK, 1999, pp. 126–136]. Unlike the bound of Cvetković et al., the new SDP bound is not dominated by the Held–Karp linear programming bound, or vice versa.
ISSN: 1095-7189
DOI: 10.1137/070711141
Schools: School of Physical and Mathematical Sciences 
Rights: SIAM Journal on Optimization @ 2008 Society for Industrial and Applied Mathematics. This journal's website is locationed at
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
SJE001559.pdf228.55 kBAdobe PDFThumbnail

Citations 10

Updated on Sep 28, 2023

Web of ScienceTM
Citations 10

Updated on Sep 29, 2023

Page view(s) 10

Updated on Oct 3, 2023

Download(s) 5

Updated on Oct 3, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.