An O(log 1.5 n log log n) Approximation Algorithm for Mean Isoperimetry and Robust k-means.
Morteza Alimi, Amir Daneshgar, Mohammad-Hadi Foroughmand-Araabi · arXiv (Cornell University) · 2018
Given a weighted graph $G=(V,E)$, and $U\subseteq 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 \textsc{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(\log^{1.5}n \log\log n)$ approximation algorithm for the \textsc{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 $\mathbb{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(\log^{1.5}n \log\log n)$-approximation algorithm, whose running time is polynomial in $n$, $k$, and $d$.