文章基本信息

标题：Guruswami-Sinop Rounding without Higher Level Lasserre
本地全文：下载
作者：Amit Deshpande ; Rakesh Venkat
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：105-114
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.105
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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, the (r+1)-th generalized eigenvalue is at least OPT/(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 l_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 l_2^2 triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, the (r+1)-th generalized eigenvalue is at least OPT/(1-delta), holds.
关键词：Sparsest Cut; Lasserre Hierarchy; Metric embeddings