# [talks] S Li general exam

Melissa Lawson mml at CS.Princeton.EDU
Thu May 13 13:50:14 EDT 2010

Shi Li will present his research seminar/general exam on Wednesday May 19 at 10AM in
Room 402.  the members of his committee are:  Moses Charikar (advisor), Sanjeev Arora,
and Bob Tarjan.  Everyone is invited to attend his talk and those faculty wishing to
remain
for the oral exam following are welcome to do so.  His abstract and reading list follow
below.
----------------------------------------------------
Title : Vertex Sparsifiers and Abstract Rounding Algorithms

The notion of vertex sparsification (in particular cut-sparsification)
is introduced by Moitra. It was shown that for any graph $G = (V, E)$
and a subset of $k$ terminals $K \subset V$, there is a polynomial time
algorithm to construct a graph $H = (K, E_H)$ on just the terminal set
so that simultaneously for all cuts $(A, K-A)$, the value of the minimum
cut in $G$ separating $A$ from $K -A$ is approximately the same as the
value of the corresponding cut in $H$. Then approximation algorithms can
be run directly on $H$ as a proxy for running on $G$, yielding
approximation guarantees independent of the size of the graph. In this
work, we consider how well cuts in the sparsifier $H$ can approximate
the minimum cuts in $G$, and whether algorithms that use such reductions
need to incur a multiplicative penalty in the approximation guarantee
depending on the quality of the sparsifier.

We give a construction for $O(log k/\log \log k)$-quality cut
sparsifers, which matches the best existential result. This is done by
solving a mixed covering and matching linear programming derived from
the 0-sum game used in the existential proof.

We give the first super-constant lower bounds for how well a
cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$.
We prove a lower bound of $\Omega(\log^{1/4} k)$ -- this is
polynomially-related to the known upper
bound of $O(\log k/\log \log k)$. This is an exponential improvement on
the $\Omega(\log \log k)$ bound given in \cite{LM} which in fact was for
a stronger vertex sparsification guarantee, and did not apply to cut
sparsifiers. If we restrict the cut sparsifers to be from a linear
combination of 0-extensions, we can show a better lower bound of
$\Omega(\sqrt{log k})$. This restriction is quite reasonable since all
known constructions, as well as exsitential proofs, are based on
0-extensions.

Despite this negative result, we show that for many natural problems, we
do not need to incur a multiplicative penalty for our reduction. Roughly
speaking, we show that many graph partitioning problems can be reduced
to correspodent problems restricted to trees, at the price of $O(\log k)$ in the approximation ratio. For many problems, this saves an $O(\log k/\log\log k)$ multiplicative factor in the approximation ratio,
compared to the algorithm where we first sparsify the graph and then
solve the problem on the smaller graph. This result helps to explain the
intrinsic robustness of graph partitioning problems - i.e. why does
$O(\log k)$ always seem to be the right answer for the approximation ratio?

Papers :

[AFH+ 04] Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert
Krauthgamer, Kunal Talwar, and Eva Tardos. Approximate classification
via earthmover metrics. In SODA '04: Proceedings of the fifteenth annual
ACM-SIAM symposium on Discrete algorithms, pages 1079-1087,
Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.

[CKR01] Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation
algorithms for the 0-extension problem. In SODA '01: Proceedings of the
twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 8-16,
Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.

[FHRT03] Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal
Talwar. An improved approximation algorithm for the 0-extension problem.
In SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on
Discrete algorithms, pages 257-265, Philadelphia, PA, USA, 2003. Society
for Industrial and Applied Mathematics.

[KKL88] J. Kahn, G. Kalai, and N. Linial. The influence of variables on
boolean functions. In SFCS '88: Proceedings of the 29th Annual Symposium
on Foundations of Computer Science, pages 68-80, Washington, DC, USA,
1988. IEEE Computer Society.

[Moi09] Ankur Moitra. Approximation algorithms for multicommodity-type
problems with guarantees independent of the graph size. In FOCS, pages
3-12, 2009.

[FRT03] Fakcharoenphol, Jittat, Rao, Satish, and Talwar, Kunal: A tight
bound on approximating arbitrary metrics by tree metrics, STOC '03, ACM,
448-455, 2003

[AHK05] Arora, Sanjeev, Hazan, Elad, and Kale, Satyen: The
multiplicative weights update method: a meta algorithm and applications,
2005

[You01] Young, Neal E.: Sequential and Parallel Algorithms for Mixed
Packing and Covering, In 42nd Annual IEEE Symposium on Foundations of
Computer Science, 538-546, 2001

Books :
Computational complexity, a modern approach, by Sanjeev Arora and Boaz
Barak, 2009.
Chapters : 0 ~ 9, 11, 14, 19, 22
Appromixation Algorithms, by Vijay V. Vazirani, 2001
Chapters : 4, 11, 12, 15, 18 ~ 21, 26