Name
Abstract | ||
|---|---|---|
We prove a structure theorem for the feasible solutions of the Arora-Rao-Vazirani SDP relaxation on low threshold rank graphs and on small-set expanders. We show that if G is a graph of bounded threshold rank or a small-set expander, then an optimal solution of the Arora-Rao-Vazirani relaxation (or of any stronger version of it) can be almost entirely covered by a small number of balls of bounded radius. Then, we show that, if k is the number of balls, a solution of this form can be rounded with an approximation factor of O(sqrt {log k}) in the case of the Arora-Rao-Vazirani relaxation, and with a constant-factor approximation in the case of the k-th round of the Sherali-Adams hierarchy starting at the Arora-Rao-Vazirani relaxation. The structure theorem and the rounding scheme combine to prove the following result, where G=(V,E) is a graph of expansion \phi(G), \lambda_k is the k-th smallest eigenvalue of the normalized Laplacian of G, and \phi_k(G) = \min_{disjoint S_1,...,S_k} \max_{1 <= i <= k} \phi(S_i) is the largest expansion of any k disjoint subsets of V: if either \lambda_k >> log^{2.5} k \cdot phi(G) or \phi_{k} (G) >> log k \cdot sqrt{log n}\cdot loglog n\cdot \phi(G), then the Arora-Rao-Vazirani relaxation can be rounded in polynomial time with an approximation ratio O(sqrt{log k}). Stronger approximation guarantees are achievable in time exponential in k via relaxations in the Lasserre hierarchy. Guruswami and Sinop [GS13] and Arora, Ge and Sinop [AGS13] prove that 1+eps approximation is achievable in time 2^{O(k)} poly(n) if either \lambda_k > \phi(G)/ poly(eps), or if SSE_{n/k} > sqrt{log k log n} \cdot \phi(G)/ poly(eps), where SSE_s is the minimal expansion of sets of size at most s. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Structured program theorem,Discrete mathematics,Combinatorics,Disjoint sets,Rounding,Small set,Eigenvalues and eigenvectors,Mathematics,Bounded function,Lambda,Laplace operator |
DocType | Volume | Citations |
Journal | abs/1304.2060 | 2 |
PageRank | References | Authors |
0.38 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shayan Oveis Gharan | 1 | 323 | 26.63 |
| Luca Trevisan | 2 | 2995 | 232.34 |