Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 28, 2011, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Andrea Francke
During the last two decades or so, low-distortion embeddings became recognized as a useful toolkit for designing efficient algorithms [Indyk '01]. A project that has received considerable attention is to embed the edit distance metric into the normed space l_1. A subcase of this is to consider the Ulam metric, that is, the metric space of all permutations of length n together with the edit distance, and to embed it into l_1. Krauthgamer and Charikar have shown in 2006 that this is possible with distortion O(log n), which is close to optimal. After a brief introduction on metric embeddings, I will present their embedding and parts of the analysis as a nice example for a metric embedding with surprising connections to elements from the analysis of randomized quicksort, as prominently featured in the "Algorithms, Probability and Computing" course.
Automatic MiSe System Software Version 1.4803M | admin login