The study of approximation algorithms in 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 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 geometric properties.

 

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

We will start with a QPTAS for TSP in doubling metrics which is based on [Talwar, STOC 04].

Then we talk about PTASes for variations of TSP in doubling metrics, which is based on [Bartal, Gottlieb, Krauthgammer, STOC 12] and [Chan, Jiang, SODA 16].

We will 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.

 

Part II:

 

As suggested by Prof. Yuqing Sun, I will share my experience in doing research in HKU.

I will also introduce the research of our group.

Undergraduate and master students interested in HKU are welcome to join this session.

 

 

 

个人介绍：

 

Shaofeng Jiang is currently a 4th year PhD candidate in the department of computer science, the university of Hong Kong, under the supervision of Dr. Hubert Chan. His research interest is broadly theoretical computer science, and specifically approximation algorithms and online algorithms. He is also interested in applying techniques developed in theoretical computer science to practical problems.