# The Lazy Travelling Salesman Problem in ${\mathbb{R}}^{2}$

ESAIM: Control, Optimisation and Calculus of Variations (2007)

- Volume: 13, Issue: 3, page 538-552
- ISSN: 1292-8119

## Access Full Article

top## Abstract

top## How to cite

topPolak, Paz, and Wolansky, Gershon. "The Lazy Travelling Salesman Problem in $\mathbb{R}^2$." ESAIM: Control, Optimisation and Calculus of Variations 13.3 (2007): 538-552. <http://eudml.org/doc/249932>.

@article{Polak2007,

abstract = {
We study a parameter (σ)
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 σ 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 σ is large
enough.
},

author = {Polak, Paz, Wolansky, Gershon},

journal = {ESAIM: Control, Optimisation and Calculus of Variations},

keywords = {Travelling Salesman Problem; Legendre-Fenchel transform; travelling salesman problem},

language = {eng},

month = {6},

number = {3},

pages = {538-552},

publisher = {EDP Sciences},

title = {The Lazy Travelling Salesman Problem in $\mathbb\{R\}^2$},

url = {http://eudml.org/doc/249932},

volume = {13},

year = {2007},

}

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

DA - 2007/6//

PB - EDP Sciences

VL - 13

IS - 3

SP - 538

EP - 552

AB -
We study a parameter (σ)
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 σ 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 σ is large
enough.

LA - eng

KW - Travelling Salesman Problem; Legendre-Fenchel transform; travelling salesman problem

UR - http://eudml.org/doc/249932

ER -

## References

top- 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.
- L. Cohen, On active contour models and balloons. CVGIP, Image Underst.52 (1991) 211–218.
- R. Durbin and D. Willshaw, An analogue approach to the travelling salesman problem using an elastic net method. Nature326 (1987) 681–691.
- 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).
- E. Gurewitz, K. Rose and G.C. Fox, Constrained clustering as an optimization method. IEEE Trans. Pattern Anal. Machine Intelligence15 (1993) 785–794.
- J.B. Hiriart-Urruty and C. Lemarèchal, Convex Analysis and Minimization Algorithms II, Grundlehren der Mathematischen Wissenschaften306, Chap. 10. Springer-Verlag (1993).
- T. Kohonen, Self-Organizing Maps, Springer Series in Information Sciences30. Springer-Verlag (1997).
- S. Skyum, A simple algorithm for computing the smallest enclosing circle. Process. Lett.37 (1991) 121–125.
- 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.
- 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. Bioinformatics21 (2005) 2301–2308.
- 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.
- C. Williams, Combining deformable models and neural networks for hand-pronted digit recognition. Ph.D. thesis, University of Toronto (1994).
- A. Witkin, M. Kass and D. Terzopoulos, Snakes: Active contour models. First International Conference on Computer Vision (1987).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.