The Library
Small space representations for metric minsum kclustering and their applications
Tools
Czumaj, Artur and Sohler, Christian (2007) Small space representations for metric minsum kclustering and their applications. In: Thomas, W. and Weil, P., (eds.) STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 2224, 2007. Proceedings. Lecture Notes in Computer Science, Volume 4393 . Springer Berlin Heidelberg, pp. 536548. ISBN 9783540709176
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/9783540709183_46
Abstract
The minsum kclustering problem is to partition a metric space (P, d) into k clusters C1, . . . , Ck subset of P such that Sigma(k)(i=1), Sigma(p,q is an element of Ci) d(p, q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. Using our coresets we obtain three main algorithmic results.
The first result is a sublinear time (4 + is an element of)approximation algorithm for the minsum kclustering problem in metric spaces. The running time of this algorithm is (O) over tilde (n) for any constant k and E, and it is o(n(2)) for all k = o(log n/ log log n). Since the description size of the input is Theta(n(2)), this is sublinear in the input size.
Our second result is the first passefficient data streaming algorithm for minsum kclustering in the distance oracle model, i.e., an algorithm that uses poly (log n, k) space and makes 2 passes over the input point set arriving as a data stream.
Our third result is a sublineartime polylogarithmicfactorapproximation algorithm for the minsum kclustering problem for arbitrary values of k.
To develop the coresets, we introduce the concept of alphapreserving metric embeddings. Such an embedding satisfies properties that (a) the distance between any pair of points does not decrease, and (b) the cost of an optimal solution for the considered problem on input (P, d') is within a constant factor of the optimal solution on input (P, d). In other words, the idea is find a metric embedding into a (structurally simpler) metric space that approximates the original metric up to a factor of a with respect to a certain problem. We believe that this concept is an interesting generalization of coresets.
Item Type:  Book Item  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Series Name:  Lecture Notes in Computer Science  
Journal or Publication Title:  Stacs 2007, Proceedings  
Publisher:  Springer Berlin Heidelberg  
ISBN:  9783540709176  
ISSN:  03029743  
Book Title:  STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 2224, 2007. Proceedings  
Editor:  Thomas, W. and Weil, P.  
Official Date:  2007  
Dates: 


Volume:  Volume 4393  
Number of Pages:  13  
Page Range:  pp. 536548  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Title of Event:  24th Annual Symposium on Theoretical Aspects of Computer Science  
Location of Event:  Aachen, Germany  
Date(s) of Event:  2224 Feb 2007 
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 