On semidefinite programming relaxations of the traveling salesman problem.

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

On semidefinite programming relaxations of the traveling salesman problem.

Show simple item record

dc.contributor.author De Klerk, Etienne.
dc.contributor.author Pasechnik, Dmitrii V.
dc.contributor.author Sotirov, Renata.
dc.date.accessioned 2009-05-08T01:44:09Z
dc.date.available 2009-05-08T01:44:09Z
dc.date.copyright 2008
dc.date.issued 2009-05-08T01:44:09Z
dc.identifier.citation 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.
dc.identifier.issn 1095-7189
dc.identifier.uri http://hdl.handle.net/10220/4600
dc.description.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.
dc.format.extent 15 p.
dc.language.iso en
dc.relation.ispartofseries SIAM journal on optimization
dc.rights SIAM Journal on Optimization @ 2008 Society for Industrial and Applied Mathematics. This journal's website is locationed at http://siamdl.aip.org/.
dc.subject DRNTU::Science::Mathematics::Applied mathematics::Operational research.
dc.title On semidefinite programming relaxations of the traveling salesman problem.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.openurl http://sfxna09.hosted.exlibrisgroup.com:3410/ntu/sfxlcl3?url_ctx_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Actx&url_ver=Z39.88-2004&url_tim=2009-05-07T03%3A41%3A58-0400&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rft.spage=1559&rft.volume=19&rft.aulast=de+Klerk&rft.issn=10957189&rft_id=info%3Adoi%2F10.1137%2F070711141&rft.jtitle=SIAM+Journal+on+Optimization&rft.genre=article&rft.auinit1=E&rft.date=2008&rft.issue=4&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info%3Asid%2Faip.org%3Ascitation
dc.identifier.doi http://dx.doi.org.ezlibproxy1.ntu.edu.sg/10.1137/070711141
dc.description.version Published version

Files in this item

Files Size Format View
SJE001559.pdf 234.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record