An O(^1.5n n) Approximation Algorithm for Mean Isoperimetry and Robust k-means
share
Given a weighted graph G=(V,E), and U⊆ V, the normalized cut value for U is defined as the sum of the weights of edges exiting U divided by the number of vertices in U. The mean isoperimetry problem for weighted graphs is a generalization of the sparsest cut problem in which, given a parameter k alongside a weighted graph G=(V,E), the objective is to find k disjoint nonempty subsets of V for which the average normalized cut value of the parts is as small as possible. In this paper, we present an O(^1.5n n) approximation algorithm for the mean isoperimetry problem. Our approach is based on developing an exact dynamic programming algorithm for this problem on weighted trees. We also show how our algorithm can be utilized to approximately solve a robust version of the k-means clustering problem in R^d, in which there can be some "outlier" points, lying outside the k parts. For this, the standard k-means objective function is modified to take into account the effect of the outliers by adding some penalty function g for them. We show that for a relatively general class of penalty functions g, this problem admits an O(^1.5n n)-approximation algorithm, whose running time is polynomial in n, k, and d.
READ FULL TEXT