Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra

Details Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra

2011-12-18

arxiv.org/abs/1112.4109v2

Computer Science

Data Structures and Algorithms

18 pages

Scientific paper

We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any $\eps,\delta \in (0,1)$, given input graph $G$ and demand graph $H$ on vertex set $V$, we can find a cut $U \subseteq V$ with $\frac{w_G(U,V\setminus U)}{w_H(U,V\setminus U)}$ at most $\frac{1+\eps}{\delta}$ times the optimal non-uniform sparsest cut value, in time $n^{r/(\delta \eps)}$ provided $\lambda_r(G;H) \ge \Phi(G;H)/(1-\delta)$. Here $\lambda_r(G;H)$ is the $r$'th smallest generalized eigenvalue of the Laplacian of $G$ w.r.t that of $H$; $w_G(U,V\setminus U)$ (resp. $w_H(U,V\setminus U)$) is the weight of edges crossing the $(U,V\setminus U)$ cut in $G$ (resp. $H$); and $\Phi(G;H)$ is the sparsity of the optimal cut. In words, we show that non-uniform sparsest is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the $r$'th smallest eigenvalue of the {\em normalized} Laplacian playing the role of $\lambda_r(G)$ in the latter two cases. Our proof is based on an $\ell_1$-embedding of vectors from a semidefinite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting $\ell_1$-embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of {\em edges} rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.

Affiliated with

Also associated with

No associations

Rating

Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lasserre SDPs, $\ell_1$-embeddings, and approximating non-uniform sparsest cut via generalized spectra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25655