Min Sum Clustering with Penalties

Traditionally, clustering problems are investigated under the assumption that all objects must be clustered. A shortcoming of this formulation is that a few distant objects, called outliers, may exert a disproportionately strong influence over the solution. In this work we investigate the k-min-sum clustering problem while addressing outliers in a meaningful way. Given a complete graph G = (V,E), a weight function w : E →IN0 on its edges, and $p \rightarrow {\it {IN}_{o}}$ a penalty function on its nodes, the penalized k-min-sum problem is the problem of finding a partition of V to k+1 sets, {S1,...,Sk+1}, minimizing $\sum_{i=1}^{k}$w(Si)+p(Sk+1), where for S⊆Vw(S) = $\sum_{e=\{{\it i},{\it j}\} \subset {\it S}}$we, and p(S) = $\sum_{i \in S}{^p_i}$. We offer an efficient 2-approximation to the penalized 1-min-sum problem using a primal-dual algorithm. We prove that the penalized 1-min-sum problem is NP-hard even if w is a metric and present a randomized approximation scheme for it. For the metric penalized k-min-sum problem we offer a 2-approximation.