Seminario Interdipartimentale di Algoritmica  

Monday, April 10, 2006, 12:00 noon
Lower Stretch Spanning Trees
Michael Elkin, Ben-Gurion University

DIS - Department of Computer and System Sciences
Room C3, second floor

Abstract:

In a seminal paper of Alon, Karp, Peleg and West, 1992, the authors considered the problem of constructing a spanning tree T with a low average stretch for a given undirected possibly weighted n-vertex graph G = (V,E).

For an edge e = {u,w} in E, the **stretch** of e with respect to T, denoted str(e,T), is the ratio between the distances between u and w in T and in G. The **average-stretch** of a tree T is

    avgstr(T) = (1/|E|) * \sum_{e \in E} str(e,T).

Alon et al. showed that for every graph G there exists a spanning tree T with avgstr(T) = exp{O(\sqrt{\log n \log\log n})}, and that there exist (infinitely many) graphs G such that for every spanning tree T for G, avgstr(T) = \Omega(\log n). Closing the gap between the upper and lower bounds of Alon et al. is a challenging open problem.

In a recent joint work with Emek, Spielman and Teng we showed an upper bound of O(\log^2 n \log\log n) for the problem. Our techniques were also used by Dhamdhere, Gupta and Racke to further improve the upper bound to O(\log^2 n). In this talk I will show an outline of the proofs of  improved bounds, and present some directions for future work.