TR02-025 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Publication: 28th April 2002 14:39

Downloads: 1804

Keywords:

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well as for points in d-dimensional space

where the distance between two points x,y is measured by

the square of the Euclidian distance (notice that

this is not a metric). Our algorithms

can be modified to handle other objective functions, such as minimizing the sum

over all clusters of the total distance to the best choice for

cluster center.