mirage

On semidefinite programming relaxations of the traveling salesman problem.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

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

Statistics

Total views

All Items Views
On semidefinite programming relaxations of the traveling salesman problem. 248

Total downloads

All Bitstreams Views
SJE001559.pdf 206

Top country downloads

Country Code Views
United States of America 112
Russian Federation 20
Singapore 19
China 15
Lebanon 10

Top city downloads

city Views
Mountain View 41
Singapore 19
Redmond 14
Bellevue 7
Seattle 7

Downloads / month

  2014-02 2014-03 2014-04 total
SJE001559.pdf 0 0 3 3