research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Publication

Type of publication:Inproceedings
Entered by:
TitleGeometric Clustering to Minimize the Sum of Cluster Sizes
Bibtex cite IDRACTI-RU1-2005-68
Booktitle 13th European Symposium on Algorithmics (ESA 2005)
Year published 2005
Pages 460-471
Publisher Springer Berlin / Heidelberg
URL http://www.lsi.upc.edu/~algo05/?cmd=esa2005
Abstract
We study geometric versions of the min-size k-clustering problem, a clustering problem which generalizes clustering to minimize the sum of cluster radii and has important applications. We prove that the problem can be solved in polynomial time when the points to be clus- tered are located on a line. For Euclidean spaces of higher dimensions, we show that the problem is NP-hard and present polynomial time ap- proximation schemes. The latter result yields an improved approximation algorithm for the related problem of k-clustering to minimize the sum of cluster diameters.
Authors
Bilo, V.
Caragiannis, Ioannis
Kaklamanis, Christos
Kanellopoulos, Panagiotis
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
fulltext.pdf (main file)
 
Publication ID619