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://www.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://www.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://www.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://www.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 :
