Minimum dilation trees- Part II

On the last day of the Dagstuhl week we (Christian Knauer and Michiel Smid) finally made some small progress. We were able to prove the following: Let G=(V,E) be a metric graph that contains a minimum dilation tree with dilation D. Given any t-spanner G' of G it hold that G' contains a tree of dilation O(t^2D^2). For some special cases it seems that we can obtain slightly better bounds. For example for a Delaunay triangulation of points in the Euclidean space where the bound probably is O(tD^2). Anyway, the proof is non-constructive so the main problem still remains. How can we find such a tree?

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.

Why dense outliers?

Many people asked us (not really, but it's a good way to start a blog) about the name of the blog. Joachim came up with the word `outlier' since we sometime feel like we're very far from the real theory action and we're like outliers among Australia's overwhelming majority of applied cs researchers. We're often dreaming about the good times, when we were doing our PhDs or postdocs in more theory intense places. Tasos came up with the word `dense' to describe our intellectual capacity.

The aim of this blog is to have a forum for us, for other Australian cs theoreticians (we know you're out there!) and for anyone else that wants to discuss cs theory stuff that may or may not be related to Australia - this really narrows it down.