Abstract

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 22k-Clustering, and l22k-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 22 instances, the points are in R d and the distance between two points x,y is measured by x−y22 (notice that (R d, ⋅ 22 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.

Keywords

Computer scienceCluster analysisArtificial intelligence

Affiliated Institutions

Related Publications

Publication Info

Year
2003
Type
article
Pages
50-58
Citations
158
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

158
OpenAlex

Cite This

W. Fernandez de la Véga, Marek Karpiński, Claire Kenyon et al. (2003). Approximation schemes for clustering problems. , 50-58. https://doi.org/10.1145/780542.780550

Identifiers

DOI
10.1145/780542.780550