
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
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 minmax 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 equalsize,
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 fixedminor we improve this guarantee to $O(1)$. Note that the
special case $\rho = 1/2$ is the wellknown 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 edgeexpansion, 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}.