Approximation schemes for network design problems in doubling metrics

Abstract

Network design problems are important subjects in the study of approximation algorithms. The key challenge of network design problems is to find light networks with some specific connectivity constraints. Among the network design problems, the Traveling Salesman Problem (TSP) and the Steiner Tree Problem (STP) are the two extensively studied ones. In the TSP, the goal is to find a minimum tour that visiting all the given vertices, while the STP requires a minimum graph that connects all the given terminals (which is a subset of vertices).

The seminal result by Arora 96' gave PTASs for several network design problems, including the TSP and STP in Euclidean spaces. However, the status for the problems in general bounded dimensional metric spaces was largely open, particularly in doubling metrics.

A doubling metric is a metric space with bounded doubling dimension. Doubling dimension is a popular dimensionality measure that captures the bounded local growth rate of a metric space. This notion well generalizes the Euclidean dimension, while it does not require any specific property in Euclidean spaces such as vector representation and geometry properties.

[STOC 2004: Talwar] gave a QPTAS for the TSP in doubling metrics. Only until recently, [STOC 2012: Bartal, Gottlieb, Krauthgamer] improved it to a PTAS. We continue this line of research, and we study the Traveling Salesman Problem with Neighborhoods (TSPN), and the Steiner Forest Problem (SFP) in doubling metrics, where the TSPN is a generalization of the TSP, and the SFP is a generalization of the STP. We gave PTASs in doubling metrics for both problems.

Our results are based on a generalized framework proposed by [STOC 2012: Bartal, Gottlieb, Krauthgamer] that gave a PTAS for the TSP in doubling metrics. We generalize their framework so that it is applicable to the TSPN and the SFP. Moreover, we improve their framework so that the dependence of doubling dimension in the running time is reduced. Also, we introduce new techniques to deal with the connectivity of regions for the TSPN, and we invent novel approaches to address the difficulty caused by multiple components in a solution and the present of Steiner points for the SFP.

We conclude with open questions for future works.