Tuesday, July 24, 2007

This week I'm attending the Korean Workshop on Computational Geometry at Dagstuhl in Germany (more on this in a later post). The first day was dominated by open questions and some very nice problems were presented. Panos Giannopoulos stated the problem of approximating a minimum dilation path/tour/tree. It is known that these problems are NP-hard (see for example Cheong, Haverkort and Lee'07) but can we find good approximation algorithms? There is an algorithm by Badoiu, Indyk and Sidiropoulos from SODA 2007 that embeds a metric into a tree metric with distortion (c \log n)^{O(\sqrt{\log \delta}), where c is the best distortion that can be achieved. Using this one can obtain a (\log n)^{O(\sqrt{\log n}) approximation of a minimum dilation tree. Of course it's not very good and it should be possible to achieve a much better bound in our special case. However, our only result so far is that there exists a (1+x)-approximation of a minimum dilation tree that has O(1/x) degree, for any x>0. It's a small observation but it might help.

No comments:

Post a Comment