Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

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 k})$-approximation algorithm. This improves over an $O(\log2 n)$ approximation for the second version due to Svitkina and Tardos \cite{ST04}, and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an improved $O(1)$-approximation algorithm for graphs that exclude any fixed minor. Along the way, we study the $\rho$-Unbalanced Cut problem, whose goal is to find, 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)}})$; when the input graph excludes a fixed-minor we improve this guarantee to $O(1)$. Note that the special case $\rho = 1/2$ is the well-known Minimum Bisection problem, and indeed our bounds generalize those of Arora, Rao and Vazirani \cite{ARV08} and of Klein, Plotkin, and Rao~\cite{KPR93}. Our algorithms work also for the closely related Small Set Expansion (SSE) problem, which asks for a set $S\subseteq V$ of size $0<|S| \leq \rho n$ with minimum 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 follows from R\"acke~\cite{Racke08}.

Questions and Answers

You need to be logged in to be able to post here.