The lazy travelling salesman problem in $\mathbb {R}^2$

Polak, Paz; Wolansky, Gershon

doi:10.1051/cocv:2007025

Geodesic

Parcourir par

The lazy travelling salesman problem in

ℝ^{2}

Polak, Paz ; Wolansky, Gershon

ESAIM: Control, Optimisation and Calculus of Variations, Tome 13 (2007) no. 3, pp. 538-552

Voir la notice de l'article provenant de la source Numdam

Résumé

We study a parameter ( $σ$ ) dependent relaxation of the Travelling Salesman Problem on $ℝ^{2}$ . The relaxed problem is reduced to the Travelling Salesman Problem as $σ \to$ 0. For increasing $σ$ it is also an ordered clustering algorithm for a set of points in $ℝ^{2}$ . A dual formulation is introduced, which reduces the problem to a convex optimization, provided the minimizer is in the domain of convexity of the relaxed functional. It is shown that this last condition is generically satisfied, provided $σ$ is large enough.

DOI : 10.1051/cocv:2007025

Classification : 49K30, 49K35, 65K10
Keywords: travelling Salesman problem, Legendre-Fenchel transform

@article{COCV_2007__13_3_538_0,
     author = {Polak, Paz and Wolansky, Gershon},
     title = {The lazy travelling salesman problem in $\mathbb {R}^2$},
     journal = {ESAIM: Control, Optimisation and Calculus of Variations},
     pages = {538--552},
     publisher = {EDP-Sciences},
     volume = {13},
     number = {3},
     year = {2007},
     doi = {10.1051/cocv:2007025},
     mrnumber = {2329175},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/cocv:2007025/}
}

TY  - JOUR
AU  - Polak, Paz
AU  - Wolansky, Gershon
TI  - The lazy travelling salesman problem in $\mathbb {R}^2$
JO  - ESAIM: Control, Optimisation and Calculus of Variations
PY  - 2007
SP  - 538
EP  - 552
VL  - 13
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/cocv:2007025/
DO  - 10.1051/cocv:2007025
LA  - en
ID  - COCV_2007__13_3_538_0
ER  -

%0 Journal Article
%A Polak, Paz
%A Wolansky, Gershon
%T The lazy travelling salesman problem in $\mathbb {R}^2$
%J ESAIM: Control, Optimisation and Calculus of Variations
%D 2007
%P 538-552
%V 13
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/cocv:2007025/
%R 10.1051/cocv:2007025
%G en
%F COCV_2007__13_3_538_0

Polak, Paz; Wolansky, Gershon. The lazy travelling salesman problem in $\mathbb {R}^2$. ESAIM: Control, Optimisation and Calculus of Variations, Tome 13 (2007) no. 3, pp. 538-552. doi: 10.1051/cocv:2007025

Cité par Sources :