Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2002 Copyright 2002 Universität Bonn, Institut für Informatik, Abt. V
8978

May 13, 2002

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering
W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon and Yuval Rabani
[Download PostScript] [Download PDF]

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 Rd where the distance between two points x, y is measured by ||x - y||22 (notice that Rd, ||.||22) is not a metric space). 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.

Last Change: 11/05/14 at 10:25:33
 English
Universität Bonn -> Institut für Informatik -> Abteilung V