The lazy travelling salesman problem in 2
ESAIM: Control, Optimisation and Calculus of Variations, Tome 13 (2007) no. 3, pp. 538-552.

We study a parameter (σ) dependent relaxation of the Travelling Salesman Problem on 2 . 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 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
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] A.J. Abrantes and J.S. Marques, Unified approach to snakes, elastic nets and Kohonen maps, in Proceeding ICASSP IEEE International Conference on Acoustics Speech Signal Process (1995) 3427-3430.

[2] L. Cohen, On active contour models and balloons. CVGIP, Image Underst. 52 (1991) 211-218. | Zbl

[3] R. Durbin and D. Willshaw, An analogue approach to the travelling salesman problem using an elastic net method. Nature 326 (1987) 681-691.

[4] S.J. Gilson and R.I. Damper, An empirical comparison of neural techniques for edge linking of images. Neural Comput. Appl. 6 (1997) 64-78 (Historical Archive).

[5] E. Gurewitz, K. Rose and G.C. Fox, Constrained clustering as an optimization method. IEEE Trans. Pattern Anal. Machine Intelligence 15 (1993) 785-794.

[6] J.B. Hiriart-Urruty and C. Lemarèchal, Convex Analysis and Minimization Algorithms II, Grundlehren der Mathematischen Wissenschaften 306, Chap. 10. Springer-Verlag (1993). | MR | Zbl

[7] T. Kohonen, Self-Organizing Maps, Springer Series in Information Sciences 30. Springer-Verlag (1997). | MR | Zbl

[8] S. Skyum, A simple algorithm for computing the smallest enclosing circle. Process. Lett. 37 (1991) 121-125. | Zbl

[9] R. Szeliski, R. Durbin and A. Yuille, An analysis of the elastic net approach to the travelling salesman problem. Neural Comput. 1 (1989) 348-358.

[10] D. Tsafrir, I. Tsafrir, L. Ein-Dor, O. Zuk, D.A. Notterman and E. Domany, Sorting points into neighborhoods (spin): data analysis and visualization by ordering distance matrices. Bioinformatics 21 (2005) 2301-2308.

[11] E. Welzl, 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] C. Williams, Combining deformable models and neural networks for hand-pronted digit recognition. Ph.D. thesis, University of Toronto (1994).

[13] A. Witkin, M. Kass and D. Terzopoulos, Snakes: Active contour models. First International Conference on Computer Vision (1987).

Cité par Sources :