Guruswami-Sinop Rounding without Higher Level Lasserre

Guruswami and Sinop give a \(O(1/\delta)\) 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, nam...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2014-06
Main Authors: Deshpande, Amit, Venkat, Rakesh
Format: Article
Language:English
Subjects:
Approximation
Eigenvalues
Mathematical analysis
Nonlinear programming
Rounding
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Guruswami and Sinop give a \(O(1/\delta)\) 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, \(\lambda_{r+1} \geq \Phi^{*}/(1-\delta)\). 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 \(\ell_{2}^{2}\) triangle inequality constraints. This results in a \(O(r/\delta^{2})\) approximation guarantee for the non-uniform Sparsest Cut problem by adding only \(\ell_{2}^{2}\) triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, \(\lambda_{r+1} \geq \Phi^{*}/(1-\delta)\), holds.
ISSN:2331-8422