In which we complete the analysis of the ARV rounding algorithm
We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio .
In previous lectures, we reduced the analysis of the algorithm to the following claim.