A Generalized Minimum Cost k-Clustering
We consider the problems of set partitioning into k clusters with minimum total cost and minimum of the maximum cost of a cluster. The cost function is given by an oracle, and we assume that it satisfies some natural structural constraints. That is, we assume that the cost function is monotone, the cost of a singleton is zero, and we assume that for all S boolean AND S' not equal phi the following holds c(S) + c(S') >= c(S boolean OR S'). For the problem of minimizing the maximum cost of a cluster we present a (2k - 1)-approximation algorithm for k >= 3, a 2-approximation algorithm for k = 2, and we also show a lower bound of k on the performance guarantee of any polynomial-time algorithm. For the problem of minimizing the total cost of all the clusters, we present a 2-approximation algorithm for the case where k is a fixed constant, a (4k - 3)-approximation where k is unbounded, and we show a lower bound of 2 on the approximation ratio of any polynomial-time algorithm. Our lower bounds do not depend on the common assumption that P not equal NP.
clustering oracle cost functions approximation algorithms