Lecture Notes on the ARV Algorithm for Sparsest Cut

Thomas Rothvoss

One of the landmarks in approximation algorithms is the $O(\sqrt{\log n})$-approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The al…