The Lazy Travelling Salesman Problem in ℝ 2

Paz Polak; Gershon Wolansky

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

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

Abstract

top
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.

How to cite

top

Polak, 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
  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.  
  3. R. Durbin and D. Willshaw, An analogue approach to the travelling salesman problem using an elastic net method. Nature326 (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 Intelligence15 (1993) 785–794.  
  6. J.B. Hiriart-Urruty and C. Lemarèchal, Convex Analysis and Minimization Algorithms II, Grundlehren der Mathematischen Wissenschaften306, Chap. 10. Springer-Verlag (1993).  
  7. T. Kohonen, Self-Organizing Maps, Springer Series in Information Sciences30. Springer-Verlag (1997).  
  8. S. Skyum, A simple algorithm for computing the smallest enclosing circle. Process. Lett.37 (1991) 121–125.  
  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. Bioinformatics21 (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).  

NotesEmbed ?

top

You must be logged in to post comments.