We study a parameter () dependent relaxation of the Travelling Salesman Problem on . The relaxed problem is reduced to the Travelling Salesman Problem as 0. For increasing it is also an ordered clustering algorithm for a set of points in . 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.
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/cocv:2007025/
[1] and, Unified approach to snakes, elastic nets and Kohonen maps, in Proceeding ICASSP IEEE International Conference on Acoustics Speech Signal Process (1995) 3427-3430.
[2] , On active contour models and balloons. CVGIP, Image Underst. 52 (1991) 211-218. | Zbl
[3] and, An analogue approach to the travelling salesman problem using an elastic net method. Nature 326 (1987) 681-691.
[4] and, An empirical comparison of neural techniques for edge linking of images. Neural Comput. Appl. 6 (1997) 64-78 (Historical Archive).
[5] , and, Constrained clustering as an optimization method. IEEE Trans. Pattern Anal. Machine Intelligence 15 (1993) 785-794.
[6] and, Convex Analysis and Minimization Algorithms II, Grundlehren der Mathematischen Wissenschaften 306, Chap. 10. Springer-Verlag (1993). | MR | Zbl
[7] , Self-Organizing Maps, Springer Series in Information Sciences 30. Springer-Verlag (1997). | MR | Zbl
[8] , A simple algorithm for computing the smallest enclosing circle. Process. Lett. 37 (1991) 121-125. | Zbl
[9] , and, An analysis of the elastic net approach to the travelling salesman problem. Neural Comput. 1 (1989) 348-358.
[10] ,,,, and, Sorting points into neighborhoods (spin): data analysis and visualization by ordering distance matrices. Bioinformatics 21 (2005) 2301-2308.
[11] , Smallest enclosing disks (balls) and ellipsoids, in New Results and New Trends in Computer Science, H. Maurer Ed., Lect. Notes Comput. Sci. (1991) 359-370.
[12] , Combining deformable models and neural networks for hand-pronted digit recognition. Ph.D. thesis, University of Toronto (1994).
[13] , and, Snakes: Active contour models. First International Conference on Computer Vision (1987).
Cité par Sources :
