Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, June 07, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Anastasios Sidiropoulos (TTY-C Chicago)
Over the past 15 years, metric embeddings have become an essential tool in theoretical computer science. In this talk I will survey some recent results on embeddings of the shortest-path metrics of graphs into spaces with simpler topology. Such mappings can be used for example to embed a graph of small genus into a planar graph, or a graph of small pathwidth into a tree, with only a small change on the underlying geometry. I will also discuss some implications for the design of approximation algorithms, the Sparsest-Cut problem, and the Gupta-Newman-Rabinovich-Sinclair conjecture.
Based on joint work with Glencora Borradaile, Piotr Indyk, and James R. Lee.
Automatic MiSe System Software Version 1.4803M | admin login