On 17.01.2008 at 12.20 in S5, there is the following noon lecture:
Probabilistic Embeddings of Bounded Genus Graphs Into Planar Graphs
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010