## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, November 14, 2006, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Fabian Kuhn (Microsoft Research Silicon Valley, California)

## Reconstructing Approximate Tree Metrics

If any four points of a metric space can be isometrically embedded into a tree, the whole metric can be isometrically embedded into a tree. This is called the four-point condition and a metric space satisfying the four-point condition is called a tree metric. We introduce a parameter eps and consider a natural relaxation of the four-point condition such that tree metrics have eps=0 and such that any metric space has an eps in [0,1]. We call our relaxation the eps-four-point condition. We show that there are constants c_1 and c_2 such that any metric space which satisfies the eps-four-point condition can be embedded into a tree with distortion (1+eps)^(c_1*log n) and such that for every eps in [0,1], there is a metric space satisfying the eps-four-point condition which does not embed into a tree with distortion less than (1+eps)^(c_2*log n). The lower bound implies that for every eps in [0,1], there is a metric space such that any set of four points can be embedded into a tree with distortion 1+eps but where any tree embedding has distortion at least (1+eps)^(c_2*log n).

Joint work with Ittai Abraham, Dahlia Malkhi, and Kunal Talwar.

Information for students and suggested topics for student talks