A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling MetricsReportar como inadecuado

A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Discrete and Computational Geometry

, Volume 46, Issue 4, pp 704–723

First Online: 18 March 2011Received: 10 June 2010Revised: 09 February 2011Accepted: 18 February 2011


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 quasi-polynomial time approximation scheme 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 similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another.

Our result generalizes the polynomial time approximation scheme PTAS for TSPN on the Euclidean plane by Mitchell in SODA, pp. 11–18, 2007 and the QPTAS for TSP on doubling metrics by Talwar in 36th STOC, pp. 281–290, 2004. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

KeywordsTraveling salesman problem with neighborhoods Quasi-polynomial time approximation scheme Doubling metrics A preliminary version of the paper has appeared in SODA 2010.

This research was done while T-H.H. Chan was at Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany.

Download to read the full article text

Autor: T.-H. Hubert Chan - Khaled Elbassioni

Fuente: https://link.springer.com/

Documentos relacionados