Geometric Embeddings and Graph Partitioning
Sanjeev Arora, Satish B. Rao · 2008
In these notes, we will focus on approximating the NP-hard problem of finding balanced cuts where we require both sets of cut vertices to be large. Specifically, this is an exposition of the STOC’04 breakthrough result of Arora, Rao and U. Vazirani [1]. The main result is a O( √ log n) approximation algorithm for a variety of graph partitioning problems including Sparsest Cut, Edge Expansion and Graph Conductance. Thus improving on the previous best O(logn) approximation of Leighton and Rao [3]. We will only give a O(log n) approximation algorithm for balanced cut. However, the tools and techniques developed is the basis of obtaining O( √ logn) approximation in a variety of related problems.