Speaker: Shaofeng Jiang The University of Hong Kong
Time: 2017-02-24 16:30-2017-02-24 17:30
Venue: FIT 1-222

Abstract:

The study of approximation algorithms in bounded dimensional Euclidean spaces is quite fruitful. For instance, the celebrated result by [Arora 98] presents PTASes for several variations of TSP and Stiener tree problems. However, the techniques heavily reply on the geometry of the Euclidean spaces, and it is an important question that whether the bounded dimensionality is sufficient for the existence of PTASes, without the need of Euclidean properties (such as vector representation and geometric properties).

The notion of doubling dimension is widely considered for measuring the intrinsic dimensionality of a metric space. Previous works showed that doubling dimension is more general than many measure of dimensionality. In particular, it is a generalization of Euclidean dimension while it does not possess Euclidean properties.

In this talk, we discuss several recent results on approximation algorithms in doubling metrics (metric spaces with bounded doubling dimension).

We start with an introduction to doubling metrics. Then we talk about a QPTAS for TSP in doubling metrics which is based on [Talwar, STOC 04]., PTASes for variations of TSP in doubling metrics, which is based on [Bartal, Gottlieb, Krauthgammer, STOC 12] and [Chan, Jiang, SODA 16]. 

We also introduce a very recent result - a PTAS for the Stiener forest problem in doubling metrics, which is based on [Chan, Hu, Jiang, FOCS 16].

We conclude by proposing some open questions.