### DIMACS Theoretical Computer Science Seminar

Title: Vertex Sparsification

Speaker: **Ankur Moitra**, Institute for Advanced Study

Date: Wednesday, October 12, 2011 11:00-12:00pm

Location: CoRE Bldg, CoRE 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Suppose we are given a gigantic communication network, but are only interested
in a small number of nodes (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.

In fact, 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).

Additionally, we apply these ideas to obtain a master theorem for graph
partitioning problems - as long as the integrality gap of a standard linear
programming relaxation is bounded on trees, then the integrality gap is at most
a logarithmic factor larger for general networks. This result implies optimal
bounds for many well studied graph partitioning problems as a special case, and
even yields optimal bounds for more challenging problems that had not been
studied before. Morally, these results are all based on the idea that even
though the structure of optimal solutions can be quite complicated, these
solution values can be approximated by crude (even linear) functions.

See: http://paul.rutgers.edu/~yixinxu/theory-fall11.html