Journal article
On semidefinite programming relaxations of the traveling salesman problem
- 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. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proc. 7th Int. IPCO Conference, Springer, London, 1999, pp. 126--136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
Actions
Access Document
- Publisher copy:
- 10.1137/070711141
Authors
- Journal:
- SIAM J. Optim. More from this journal
- Volume:
- 19
- Issue:
- 4
- Pages:
- 1573
- Publication date:
- 2009-02-11
- DOI:
- EISSN:
-
1095-7189
- ISSN:
-
1052-6234
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:420929
- UUID:
-
uuid:ebaaf202-7b89-44fd-b288-f417b002d981
- Local pid:
-
pubs:420929
- Source identifiers:
-
420929
- Deposit date:
-
2013-11-16
- ARK identifier:
Terms of use
- Copyright date:
- 2009
- Notes:
-
18 pages, 1 figure (corrects the figure in the published version),
LaTeX, MetaPost for the figure
If you are the owner of this record, you can report an update to it here: Report update to this record