The Taub Faculty of Computer Science Events and Talks

We study graph partitioning problems from a min-max perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equal-size, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n}\log^{3/2} k)$-approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the version of separating $k$ given terminals due to Svitkina and Tardos \cite{ST04}, and roughly $O(k\log n)$ approximation for the version where the parts need to be of equal size that follows from other previous work.

The main tool we use is a new approximation algorithm for \emph{$\rho$-unbalanced-cut}, the problem of finding in an input graph $G=(V,E)$ a set $S\subseteq V$ of size $|S|=\rho n$ that minimizes the number of edges leaving $S$. We provide a bicriteria approximation of $O(\sqrt{\log{n}\log{(1/\rho)}})$ for this problem. Note that the special case $\rho = 1/2$ is just the \emph{minimum bisection} problem, and indeed our bound generalizes that of Arora, Rao and Vazirani \cite{ARV08} which only applies to the case where $\rho = \Omega(1)$. Our algorithm also works for the closely related \emph{small-set-expansion} problem, which asks for a set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum conductance (edge-expansion), and was suggested recently by Raghavendra and Steurer~\cite{RS10}. In fact, our algorithm handles more general, weighted, versions of both problems. Previously, an $O(\log n)$ true approximation for both $\rho$-unbalanced-cut and small-set-expansion was known following from R\"acke~\cite{Racke08}.

Joint work with: Nikhil Bansal, Robi Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan and Seffi Naor.