טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPaz Pollack
SubjectLazy Traveling Salesman Problem
DepartmentDepartment of Applied Mathematics
Supervisor Full Professor Wolansky Gershon


Abstract

In this thesis we deal with the Euclidean Traveling Salesman Problem (ETSP) by tools of convex analysis. We also generalize it is to a problem with a continuous cost function named the Lazy Traveling Salesman Problem (LTSP).

In this research we consider the LTSP in the 2-dimensional plane. Given a set V of n points (cities) in the plane we would like to find a tour that minimizes two demands. The first demand is to decrease the sum of squares of Euclidean distances between the path and the n points. The second is to decrease the length of the path as much as possible. The tradeoff between these two demands is determined by a parameter It will be shown that the ETSP is a limit case of the LTSP when is small. On the other hand, the optimal tours for large usually forces partitions into less than n subsets of V hence we get a clustering problem associating each subset with a vertex of the optimal polygon solution. This partitions can be computed in a polynomial time for almost every set V of points in the plane and for every Both the non convex problems the ETSP and the LTSP can be presented as minima of sets of n! convex functions on . These presentations with Legendre-Fenchel transform give lower bounds which have a nice geometrical interpretation.