On semidefinite programming relaxations of the traveling salesman problem

• المؤلفون الرئيسيون: De Klerk, Etienne., Pasechnik, Dmitrii V., Sotirov, Renata.
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2009
• الموضوعات: DRNTU::Science::Mathematics::Applied mathematics::Operational research
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/91852; http://hdl.handle.net/10220/4600; 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
• المؤسسة: Nanyang Technological University

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. K...