 33 views
 35 downloads
Approximation Algorithms for Min Sum kClustering and Balanced kMedian

 Author / Creator
 Sivakumar, Rohit

In this thesis, we consider two closely related clustering problems, Min Sum kClustering (MSkC) and Balanced kMedian (BkM). In Min Sum kclustering, one is given a graph and a parameter k, and has to partition the vertices in the graph into k clusters to minimize the sum of pairwise distances between vertices in the same cluster. In the Balanced kMedian problem, one is given the same set of input, and has to partition the vertices into k clusters, where each cluster is centered at a unique vertex, while minimizing the total assignment costs for the points in the metric; here the cost of assigning a vertex j to a cluster C, centered at c is equal to C times the (j,c) distance. The most important contribution of this thesis is an O(log n)approximation for both these problems, where n is number of vertices in the input graph. Our approximation for general metrics uses probabilistic embeddings into Hierarchically Separated Trees (HSTs). More specifically, we prove that both MSkC and BkM have constant approximation algorithms on HSTs. In addition to these algorithms, we prove hardness results for both BkM and a generalized version of BkM, and give an exact algorithm for BkM on line metrics.

 Subjects / Keywords

 Graduation date
 201511

 Type of Item
 Thesis

 Degree
 Master of Science

 License
 This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for noncommercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.