Personal tools
You are here: Home CG seminar 2019 Improved bounds for the Traveling Salesman Problem with Neighborhoods
« December 2018 »
December
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

Improved bounds for the Traveling Salesman Problem with Neighborhoods

Wednesday, November 21st, 2018, 16:10

Schreiber 309

underline

Improved bounds for the Traveling Salesman Problem with Neighborhoods

Ioana Bercea, TAU

Abstract:

Given a set of n disks of radius R in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all of the disks. The problem is a generalization of the classical Traveling Salesman Problem (TSP) on points and has been widely studied in the literature. For the case of disjoint uniform disks of radius R, Dumitrescu and Mitchell [2003] show that the optimal TSP tour on the centers of the disks is a 3.547-approximation to the TSPN version. The core of their analysis is based on bounding the detour that the optimal TSPN tour has to make in order to visit the centers of each disk and shows that it is at most 2Rn in the worst case. Hame, Hyytia and Hakula [2011] asked whether this bound is tight when R is small and conjectured that it is at most \sqrt{3}Rn.

In this talk, we will further investigate this question and derive structural properties of the optimal TSPN tour to describe the cases in which the bound is smaller than 2Rn. Specifically, we show that if the optimal TSPN tour is not a straight line, at least one of the following is guaranteed to be true: the bound is smaller than 2Rn or the TSP on the centers is a 2-approximation (best we can get with this heuristic). This leads to an improved overall approximation factor for the problem. Along the way, we will uncover ways in which the TSPN problem is structurally different from the classical TSP.

 
 
Document Actions