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
8983

07.11.2002

Approximation Schemes for Clustering Problems in Finite Metrics and High Dimensional Spaces
W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
[Download PostScript] [Download PDF]

We give polynomial time approximation schemes (PTASs) 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 ofthe sum of pairwise distances in a cluster. Our algorithms work for arbitrary metric spaces as well as for points in Rdwhere 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 sumover all clusters of the sum of distances to the best choice fora cluster center. The method of solution of this paper depends on some newtechniques which could be also of independent interest.

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