Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 17.01.2008 at 12.20 in S5, there is the following noon lecture:

Probabilistic Embeddings of Bounded Genus Graphs Into Planar Graphs

Anastasios Sidiropoulos

MIT

Abstract

Probabilistic embeddings of metric spaces provide a general paradigm for simplifying the input of a broad class of geometric optimization problems, and have found numerous applications to the design of approximation algorithms.

We show that every metric induced by a graph of bounded genus can be probabilistically embedded into planar graphs, with constant distortion. The embedding can be computed efficiently, given a drawing of the graph on a genus-g surface.

This result implies in particular that certain optimization problems over graphs of bounded genus, can be reduced to problems over planar graphs, with a constant loss in the objective function. There are also implications on the embeddability of bounded genus graphs into ell_1.

The talk will be self-contained.

Joint work with Piotr Indyk

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010