### March 30, Wednesday 14:15, Jacobs Building Room 303

** Title: Min-Max Graph Partitioning and Small Set Expansion. **

**Lecturer :** Roy Schwartz

**Lecturer homepage
:** http://www.cs.technion.ac.il/~schwartz/

**Affiliation :** Department of Computer Science, Technion

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.