The Lazy Travelling Salesman Problem in
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. ...