AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call α-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have diameters within α factor of one another, and each such region can designate a point such that these points are far away from one another.

Hubert Chan

--email hidden

passcode not visible

logged in users only