Goemans showed that any @math points @math in @math -dimensions satisfying @math triangle inequalities can be embedded into @math , with worst-case distortion at most @math . We extend this to the case when the points are approximately low-dimensional, albeit with average distortion guarantees. More precisely, we give an @math -to- @math embedding with average distortion at most the stable rank, @math , of the matrix @math consisting of columns @math . Average distortion embedding suffices for applications such as the Sparsest Cut problem. Our embedding gives an approximation algorithm for the problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on @math metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion @math . Furthermore, while the seminal result of Arora, Rao and Vazirani giving a @math guarantee for Uniform Sparsest Cut can be seen to imply Goemans' theorem with average distortion, our work opens up the possibility of proving such a result directly via a Goemans'-like theorem.
Kwok et al @cite_4 showed that a better analysis of Cheeger's inequality gives a @math approximation to the sparsest cut in @math -regular graphs. In particular, when @math , this gives a @math approximation for the problem. In this regime, our result gives a slightly better approximation: Assuming @math , if @math then @math yielding an @math approximation by thm:SparsestCut . Otherwise, if @math , then running a Cheeger rounding on the SDP solution would itself give a cut of sparsity @math . Thus, the better of our rounding algorithm and a Cheeger rounding on the SDP solution gives a @math -approximation to the problem.
@cite_4
1571696081 2952056253 2036322374 2950405280
Guruswami and Sinop give a @math approximation guarantee for the non-uniform Sparsest Cut problem by solving @math -level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, @math . Their key idea is a rounding technique that first maps a vector-valued solution to @math using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only @math triangle inequality constraints. This results in a @math approximation guarantee for the non-uniform Sparsest Cut problem by adding only @math triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, @math , holds. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem 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 @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -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 edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut. Arora, Rao and Vazirani [2] showed that the standard semi-definite programming (SDP) relaxation of the Sparsest Cut problem with the triangle inequality constraints has an integrality gap of O(√log n). They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture (referred to as the ARV-Conjecture) by constructing an Ω(log log n) integrality gap instance. Khot and Vishnoi [16] had earlier disproved the non-uniform version of the ARV-Conjecture.A simple "stretching" of the integrality gap instance for the Sparsest Cut problem serves as an Ω(log log n) integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in [6, 11], where it was shown that its integrality gap is bounded from above by O(√log n log log n). Let (G) be the minimum conductance of an undirected graph G, and let 0= = 2, (G) = O(k) , and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if $ is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.