The Library
Small space representations for metric minsum kclustering and their applications
Tools
Czumaj, Artur and Sohler, Christian (2009) Small space representations for metric minsum kclustering and their applications. Theory of Computing Systems, Volume 46 (Number 3). pp. 416442. doi:10.1007/s0022400992351
PDF
fulltext25.pdf  Published Version Embargoed item. Restricted access to Repository staff only  Requires a PDF viewer. Download (731Kb) 
Official URL: http://dx.doi.org/10.1007/s0022400992351
Abstract
The minsum k clustering problem is to partition a metric space (P,d) into k clusters C 1,…,C k ⊆P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}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. With our construction of coresets we obtain two main algorithmic results.
The first result is a sublineartime (4+ε)approximation algorithm for the minsum kclustering problem in metric spaces. The running time of this algorithm is $\widetilde{{\mathcal{O}}}(n)$ for any constant k and ε, and it is o(n 2) for all k=o(log n/log log n). Since the full description size of the input is Θ(n 2), this is sublinear in the input size. The fastest previously known o(log n)factor approximation algorithm for k>2 achieved a running time of Ω(n k ), and no nontrivial o(n 2)time algorithm was known before.
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, which arrives in form of a data stream in arbitrary order. It computes an implicit representation of a clustering of (P,d) with cost at most a constant factor larger than that of an optimal partition. Using one further pass, we can assign each point to its corresponding cluster.
To develop the coresets, we introduce the concept of α preserving metric embeddings. Such an embedding satisfies properties that the distance between any pair of points does not decrease and 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 goal is to find a metric embedding into a (structurally simpler) metric space that approximates the original metric up to a factor of α with respect to a given problem. We believe that this concept is an interesting generalization of coresets.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Journal or Publication Title:  Theory of Computing Systems  
Publisher:  SpringerVerlag  
ISSN:  14330490  
Book Title:  Theory of Computing Systems  
Official Date:  1 April 2009  
Dates: 


Volume:  Volume 46  
Number:  Number 3  
Page Range:  pp. 416442  
DOI:  10.1007/s0022400992351  
Status:  Not Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  NSF ITR grant CCR0313219 and DIMAP, DFG grant So 514/12, EPSRC grant EP/D063191/1  
Grant number:  CCR0313219 (NSF); 514/12 (DFG); EP/D063191/1 (EPSRC)  
Version or Related Resource:  A preliminary version of this paper appeared in Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS’07). Lectures Notes in Computer Science, vol. 4393, Aachen, Germany, February 22–24, 2007, pp. 536–548. Springer, Berlin, 2007. 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 