Czumaj, Artur and Sohler, Christian (2007) Sublinear-time approximation algorithms for clustering via random sampling. In: 12th International Conference on Random Structures and Algorithms, Poznan, Poland, 01-05 Aug 2005. Published in: Random Structures & Algorithms, Volume 30 (Number 1-2). pp. 226-256. doi:10.1002/rsa.20157 ISSN 1042-9832.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.

The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Random Structures & Algorithms
Publisher:	John Wiley & Sons, Inc.
ISSN:	1042-9832
Official Date:	January 2007
Dates:	Date Event January 2007 Published
Volume:	Volume 30
Number:	Number 1-2
Number of Pages:	31
Page Range:	pp. 226-256
DOI:	10.1002/rsa.20157
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Conference Paper Type:	Paper
Title of Event:	12th International Conference on Random Structures and Algorithms
Type of Event:	Conference
Location of Event:	Poznan, Poland
Date(s) of Event:	01-05 Aug 2005

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item