ARV on Abelian Cayley Graphs

Continuing from the previous post, we are going to prove the following result: let be a -regular Cayley graph of an Abelian group, be the normalized edge expansion of , be the value of the ARV semidefinite programming relaxation of sparsest cut on (we will define it below), and be the second smallest normalized Laplacian eigenvalue of . Then we have

which, together with the fact that and , implies the Buser inequality

and the approximation bound

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

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 .

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 .

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 with adjacency matrix , then ARV relaxation of the sparsest cut problem is the following semidefinite program.

If we denote by the optimum of the relaxation, then we claimed that

where the first inequality follows from the fact that is a relaxation of , and the second inequality is the result whose proof we begin to discuss today.

CS359G Lecture 11: ARV

In which we introduce the Arora-Rao-Vazirani relaxation of sparsest cut, and discuss why it is solvable in polynomial time.