A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a @math -partition such that the subspace corresponding to the span of its indicator vectors is @math close to the original subspace in spectral norm with @math being the minimum possible ( @math always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a @math -partition closer than @math . We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest @math -partition in a graph where each cluster have expansion at most @math provided @math where @math is the @math eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required @math .
Perhaps the simplest case of is when there is a gap between the @math smallest eigenvalue of Laplacian matrix, @math , and @math of the form ( k+1 1 . ) One might think of this as a stability criteria: It implies that all @math -partitions with maximum expansion @math are @math -close to each other. To put it in another way, approximating the optimum @math -partition is at least as easy as finding a @math -partition with minimum possible expansion among all its clusters. For the case of @math , it is trivial to show that thresholding the second smallest eigenvector of Laplacian yields @math -close partition to the optimal one. On the other hand, when @math , the best prior result is due to @cite_6 , which can find a @math -partition that is @math -close to the optimal one. In other words, when @math , there is no algorithm known to find a non-trivial approximation of the optimum @math -partition.
@cite_6
2950342785
We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var... 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. A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, @math the minimum degree, and @math the maximum degree. We show that every graph has a domatic partition with @math dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a @math -approximation algorithm for domatic number, since the domatic number is always at most @math . We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every @math , a @math -approximation implies that @math . This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with @math dominating sets, where the "o(1)" term goes to zero as @math increases. This can be turned into an efficient algorithm that produces a domatic partition of @math sets. A set X of points in @math is (k,b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms that, by sampling from a set X, distinguish between the case that X is (k,b)-clusterable and the case that X is @math -far from being (k,b')-clusterable for any given @math and for @math . By @math -far from being (k,b')-clusterable we mean that more than @math points should be removed from X so that it becomes (k,b')-clusterable. We give algorithms for a variety of cost measures that use a sample of size independent of |X| and polynomial in k and @math . Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an @math -fraction of the points in X that have optimal (or close to optimal) cost. The benefit of our algorithms is that they construct an implicit representation of such clusterings in time independent of |X|. That is, without actually having to partition all points in X, the implicit representation can be used to answer queries concerning the cluster to which any given point belongs.