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

Date and Time: Tuesday, June 28, 2011, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Andrea Francke

A Metric Embedding: Ulam Metric into l_1

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login