Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 14, 2006, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Fabian Kuhn (Microsoft Research Silicon Valley, California)
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.
Automatic MiSe System Software Version 1.4803M | admin login