Affordable Access

The lazy travelling salesman problem in $\mathbb{R}^2$

Publication Date
  • Computer Science


PDF/03/cocv0521.pdf.url ESAIM: COCV ESAIM: Control, Optimisation and Calculus of Variations Vol. 13, No 3, 2007, pp. 538–552 DOI: 10.1051/cocv:2007025 THE LAZY TRAVELLING SALESMAN PROBLEM IN R2 Paz Polak1 and Gershon Wolansky2 Abstract. We study a parameter (σ) dependent relaxation of the Travelling Salesman Problem on R2. 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 R2. 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. Mathematics Subject Classification. 49K30, 49K35, 65K10. Received February 23, 2005. Revised January 31, 2006. Published online June 20, 2007. 1. Introduction The object of this paper is to investigate an optimization problem which we name “The Lazy Travelling Salesman Problem” (LTSP). As the name suggests, it is closely related to the classical Problem of Travelling Salesman (TSP). The version of the LTSP we have in mind is as follows: let V be a set of n points v1, . . . , vn ∈ R2. Let σ > 0. Given a closed, Jordan curve Γ ⊂ R2, let L(Γ) be the length of this curve and Dist(v,Γ) the distance of a point v ∈ R2 to Γ. The object is to find such a closed curve Γ which minimize Fσ(Γ) := 1 n n∑ i=1 dist2(vi,Γ) + σL2(Γ). (1) It is easily seen that a minimal curve Γ must be a polygonal, closed curve, of at most n vertices (and edges). Given this fact, we can restrict Fσ to the set of closed polygons of (at most) n vertices and represent it as a function of �u ∈ Rn × Rn, �u = (u1, . . . , un) where uj ∈ R2, via Gσ,n(�u) := 1 n n∑ j=1 min 1≤i≤n |ui − vj |2 + σL2(�u) (2) Keywords and phrases. Travelling Salesman Problem, Legendre-Fenchel transform. 1 Weizmann Institute of Science, Rehovot, Israel. 2 Department of M

There are no comments yet on this publication. Be the first to share your thoughts.