M.Sc Student | Pollack Paz |
---|---|

Subject | Lazy Traveling Salesman Problem |

Department | Department of Applied Mathematics |

Supervisor | Professor Gershon Wolansky |

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.