CS 294 Lecture 14: ARV Analysis, Part 3

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 ${O(\sqrt {\log |V|})}$.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

CS294 Lecture 13: ARV Analysis, cont’d

In which we continue the analysis of the ARV rounding algorithm

We are continuing 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 ${O(\sqrt {\log |V|})}$.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

CS359G Lecture 14: ARV Rounding

In which we begin to discuss the Arora-Rao-Vazirani rounding procedure.

Recall that, in a graph ${G=(V,E)}$ with adjacency matrix ${A}$, then ARV relaxation of the sparsest cut problem is the following semidefinite program.

$\displaystyle \begin{array}{lll} {\rm minimize} & \frac 1 {2|E|} \sum_{u,v} A_{u,v} || {\bf x}_u - {\bf x}_v ||^2\\ {\rm subject\ to}\\ & \sum_{u,v} || {\bf x}_u - {\bf x}_v ||^2 = {|V|^2}\\ & || {\bf x}_u - {\bf x}_v||^2 \leq || {\bf x}_u - {\bf x}_w||^2 + || {\bf x}_w - {\bf x}_v||^2 & \forall u,v,w \in V\\ & \mbox{} {\bf x}_u \in {\mathbb R}^d & \forall u\in V \end{array}$

If we denote by ${ARV(G)}$ the optimum of the relaxation, then we claimed that

$\displaystyle ARV(G) \leq \phi(G) \leq O(\sqrt{\log |V|}) \cdot ARV(G)$

where the first inequality follows from the fact that ${ARV(G)}$ is a relaxation of ${\phi(G)}$, and the second inequality is the result whose proof we begin to discuss today.