Theory and Algorithms Commons^™

Tight Lower Bound For The Sparse Travelling Salesman Problem, Fredrick Mtenzi

Conference papers

The Sparse Travelling Salesman Problem (Sparse TSP) which is a variant of the classical Travelling Salesman Problem (TSP) is the problem of finding the shortest route of the salesman when visiting cities in a region making sure that each city is visited at least once and returning home at the end. In the Sparse TSP, the distance between cities may not obey the triangle inequality; this makes the use of algorithms and formulations designed for the TSP to require modifications in order to produce near-optimal results. A lower bound for optmisation problems gives us the quality guarantee of the near-optimal …