<="http://www.w3.org/1999/xhtml"> CMU Theory Lunch
Reducing Curse of Dimensionality: PTAS's for Geometric Problems in Doubling Metrics
September 6, 2017

Metric geometric optimization problems (e.g. Traveling Salesman Problem (TSP), Steiner Tree Problem (STP)) are classics of theoretical computer science and have been studied for decades. While in general metric spaces, these problems are very hard to approximate (APX-Hard), it has been shown that PTAS’s exist in more “structured” spaces. The celebrated work of Arora (1998) established a dynamic programming approach that provides PTAS’s for various geometric problems in constant dimensional Euclidean spaces. Later in 2000, Trevisan (2000) showed that there is no PTAS for TSP even in Euclidean spaces with dimension log(n).

These results suggest that low dimensionality is essential in ensuring a PTAS for TSP. However, besides low dimensionality, Arora’s framework also used geometric properties (specifically, vector representation and “squares”) in Euclidean spaces. The natural question that follows is does low dimensionality alone guarantees the existence of PTAS’s for these geometric problems?

Low dimensionality is captured by the notion of doubling metrics, which is defined as the metric spaces in which each ball can be covered by a constant number of balls of half the radius. There has been significant advances in the study of approximation algorithms in doubling metrics, starting from the work of Talwar (STOC 2004) that provides a QPTAS for TSP. The first PTAS for TSP in doubling metrics was obtained by Bartal et al. (STOC 2012). Many algorithms on other problems followed including our work for prize-collecting problems.

In this talk, I will provide a description of the structural properties of doubling metrics and an overview of these recent algorithms.

Joint work with Hubert T.-H. Chan and Shaofeng H.-C. Jiang (both from HKU).