|M.Sc Student||Paz Pollack|
|Subject||Lazy Traveling Salesman Problem|
|Department||Department of Applied Mathematics||Supervisor||Full Professor Wolansky Gershon|
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.