Semidefinite relaxations of traveling salesman problem
D. Cvetkovic, M. Cangalovic, V. Kovacevic-Vujcic
In this paper we present a discrete semidefinite
programming model of the symmetric traveling salesman
problem and its relaxation which is a linear SDP
problem. The model and its semidefinite relaxation
are based on the notion of Laplacians of graphs and
on a suitable characterization of algebraic
connectivity of graphs. Namely, we prove that a
subgraph H of a graph G is connected if and only if
certain linear transformation of the Laplacian L(H)
is positive semidefinite.
The relaxation proposed in this paper is substantially
different from the existing relaxations. Preliminary
experimental results with randomly generated examples
show that it gives considerably better bounds than
2-matching and 1-tree.
Technical Report 902-98, Laboratory for Operations
Research, Faculty of Organizational Sciences,
University of Belgrade, November 1998
Contact: [email protected]
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)