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 full item record

Title: On semidefinite programming relaxations of the traveling salesman problem.
Author: De Klerk, Etienne.; Pasechnik, Dmitrii V.; Sotirov, Renata.
Copyright year: 2008
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.
Subject: DRNTU::Science::Mathematics::Applied mathematics::Operational research.
Type: Journal Article
Series/ Journal Title: SIAM journal on optimization
School: 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/.
Version: Published version

Files in this item

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

SFX Query

- Get published version (via NTU subscribed resources)
   

DOI Query

- Get published version (via Digital Object Identifier)
   

This item appears in the following Collection(s)

Show full item record

Statistics

Total views

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

Total downloads

All Bitstreams Views
SJE001559.pdf 244

Top country downloads

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

Top city downloads

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

Downloads / month

  2014-08 2014-09 2014-10 total
SJE001559.pdf 0 0 2 2