On semidefinite programming relaxations of the traveling salesman problem

Details On semidefinite programming relaxations of the traveling salesman problem On semidefinite programming relaxations of the traveling salesman problem

2009-02-11

arxiv.org/abs/0902.1843v1

SIAM J. Optim. Volume 19, Issue 4, pp. 1559-1573 (2008)

Mathematics

Optimization and Control

18 pages, 1 figure (corrects the figure in the published version), LaTeX, MetaPost for the figure

Scientific paper

10.1137/070711141

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.

Affiliated with

Also associated with

No associations

Rating

On semidefinite programming relaxations of the traveling salesman problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On semidefinite programming relaxations of the traveling salesman problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On semidefinite programming relaxations of the traveling salesman problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-487577