Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/91852
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. | URI: | https://hdl.handle.net/10356/91852 http://hdl.handle.net/10220/4600 |
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 http://siamdl.aip.org/. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
SJE001559.pdf | 228.55 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
20
29
Updated on Mar 22, 2024
Web of ScienceTM
Citations
10
25
Updated on Oct 28, 2023
Page view(s) 10
777
Updated on Mar 28, 2024
Download(s) 10
479
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.