- Time
- 1:30 – 2:20pm, Tuesday, December 7, 2010
- Place
- CSE 305
- Speaker
- Ankur Moitra, MIT
## Abstract

The notion of exactly representing or approximately preserving certain
combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in
combinatorial optimization. In this talk, we introduce the notion of vertex cut
and flow sparsification. Here we are given a graph $G = (V, E)$ and a set of
terminals $K \subset V$ and our goal is to find one single graph $H = (K, E_H)$
on just the terminal set so that $H$ approximately preserves the congestion of
_every_ multicommodity flow in which the demands have endpoints in $K$. In
practice this implies that any optimization problem over cuts or flows can
instead be solved on $H$ as a proxy for running directly on $G$, and still
returns a solution of approximately the same value. We prove good vertex
sparsifiers exist, and we also give efficient algorithms for computing good
vertex sparsifiers. As a consequence we are able to obtain approximation
algorithms with guarantees independent of the size of the graph for a number of
graph partitioning, graph layout and multicommodity flow problems for which such guarantees were previously unknown. In fact, these results follow from a generic reduction that only requires that an optimization problem can be characterized by the value of all cuts and flows.

This talk will be loosely based on three papers, Moitra "Approximation
Algorithms for Multicommodity-Type Problems with Guarantees Independent of the
Graph Size" (FOCS 2009), Tom Leighton, Moitra "Extensions and Limits to Vertex
Sparsification" (STOC 2010), and Moses Charikar, Tom Leighton, Shi Li, Moitra
"Vertex Sparsification and Abstract Rounding Algorithms" (FOCS 2010).