Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary SeminarSeries - Monday, February 6, 2012

Linda Casals lindac at
Wed Feb 1 12:07:19 EST 2012


DIMACS/CCICADA Interdisciplinary Seminar Series Presents

Title: Vertex Sparsification

Speaker: Ankur Moitra, IAS, Princeton

Date: Monday, February 6, 2012 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University                 
             Busch Campus, Piscataway, NJ


Suppose we are given a gigantic communication network, but are only
interested in a small number of terminals (clients). There are many
routing problems we could be asked to solve for our clients. Is there
a much smaller network - that we could write down on a sheet of paper
and put in our pocket - that approximately preserves all the relevant
communication properties of the original network? As we will
demonstrate, the answer to this question is YES, and we call this
smaller network a vertex sparsifier. The approximation factor is
independent of the size of the original network and depends
sub-logarithmically on the number of terminals. In fact, for natural
arising graphs (e.g. excluding a fixed minor), this improves to a
universal constant.

Now, if we are asked to solve a sequence of optimization problems
characterized by cuts or flows, we can compute a good vertex
sparsifier ONCE and discard the original network. We can run our
algorithms (or approximation algorithms) on the vertex sparsifier as a
proxy - and still recover approximately optimal solutions in the
original network. This novel pattern saves both space (because the
network we store is much smaller) and time (because our algorithms run
on a much smaller graph).

DIMACS/CCICADA Interdisciplinary Series, Complete Spring Calendar 2012 

More information about the Dimacs-ccicada-announce mailing list