Guruswami-Sinop Rounding without Higher Level Lasserre

2014/06/27 by Deshpande, Amit, Venkat, Rakesh
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1406.7279

Abstract

Guruswami and Sinop give a O(1/δ) approximation guarantee for the non-uniform Sparsest Cut problem by solving O(r)-level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, λ_r+1 ≥ Φ^*/(1-δ). Their key idea is a rounding technique that first maps a vector-valued solution to [0, 1] using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only ℓ₂² triangle inequality constraints. This results in a O(r/δ²) approximation guarantee for the non-uniform Sparsest Cut problem by adding only ℓ₂² triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, λ_r+1 ≥ Φ^*/(1-δ), holds.

Related

• Approximating Non-Uniform Sparsest Cut via Generalized Spectra
• Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
• Lecture Notes on the ARV Algorithm for Sparsest Cut
• Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?