×

The lazy travelling salesman problem in \(\mathbb{R} ^2\). (English) Zbl 1153.90014

Summary: We study a parameter (\(\sigma\)) dependent relaxation of the travelling salesman problem on \(\mathbb{R} ^2\). The relaxed problem is reduced to the travelling salesman problem as \(\sigma\rightarrow 0\). For increasing \(\sigma\) it is also an ordered clustering algorithm for a set of points in \(\mathbb{R} ^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 \(\sigma\) is large enough.

MSC:

90C27 Combinatorial optimization
90C46 Optimality conditions and duality in mathematical programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[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 0774.68111 · Zbl 0774.68111 · doi:10.1016/1049-9660(91)90028-N
[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 1295240 | Zbl 0795.49002 · Zbl 0795.49002
[7] T. Kohonen , Self-Organizing Maps , Springer Series in Information Sciences 30. Springer-Verlag ( 1997 ). MR 1450869 | Zbl 0866.68085 · Zbl 0866.68085
[8] S. Skyum , A simple algorithm for computing the smallest enclosing circle . Process. Lett. 37 ( 1991 ) 121 - 125 . Zbl 0713.68097 · Zbl 0713.68097 · doi:10.1016/0020-0190(91)90030-L
[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 ). · Zbl 0646.68105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.