Geodesic
Semidefinite Relaxations of The Traveling Salesman Problem
Yugoslav journal of operations research, Tome 9 (1999) no. 2, p. 157
Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

We apply semidefinite programming to the symmetric traveIing salesman problem (TSP). The TSP is modeled as a problem of discrete semidefinite programming. In order to estimate the optimal objective value, a class of semidefinite relaxations of the TSP model is defined. Experimental results with randomly generated examples show that the proposed relaxation gives considerably better bounds than 2-matching and 1-tree relaxation.
Classification : 90C27 90C22
Keywords: Semidefinite programming, combinatorial optimization , traveling salesman problem, 
@article{YJOR_1999_9_2_a0,
     author = {Drago\v{s} Cvetkovi\'c and Mirjana \v{C}angalovi\'c and Vera Kova\v{c}evi\'c-Vuj\v{c}i\'c},
     title = {Semidefinite {Relaxations} of {The} {Traveling} {Salesman} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {157 },
     year = {1999},
     volume = {9},
     number = {2},
     zbl = {1006.90065},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a0/}
}
TY  - JOUR
AU  - Dragoš Cvetković
AU  - Mirjana Čangalović
AU  - Vera Kovačević-Vujčić
TI  - Semidefinite Relaxations of The Traveling Salesman Problem
JO  - Yugoslav journal of operations research
PY  - 1999
SP  - 157 
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a0/
LA  - en
ID  - YJOR_1999_9_2_a0
ER  - 
%0 Journal Article
%A Dragoš Cvetković
%A Mirjana Čangalović
%A Vera Kovačević-Vujčić
%T Semidefinite Relaxations of The Traveling Salesman Problem
%J Yugoslav journal of operations research
%D 1999
%P 157 
%V 9
%N 2
%U http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a0/
%G en
%F YJOR_1999_9_2_a0
Dragoš Cvetković; Mirjana Čangalović; Vera Kovačević-Vujčić. Semidefinite Relaxations of The Traveling Salesman Problem. Yugoslav journal of operations research, Tome 9 (1999) no. 2, p. 157 . http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a0/