Approximation schemes for clustering problems

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k -Clustering, l 2 2 k -Clustering, and l 2 2 k -Median. In the k -Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k -Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 2 2 instances, the points are in R d and the distance between two points x,y is measured by x−y 2 2 (notice that (R d , ⋅ 2 2 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

Authors

• Wenceslas Fernandez de la Vega
• Marek Karpinski
• Claire Mathieu
• Yuval Rabani

Keywords

No keywords are indexed for this paper.