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
Abstract:
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