Approximation Algorithms for Min Sum k-Clustering and Balanced k-Median

  • Author / Creator
    Sivakumar, Rohit
  • In this thesis, we consider two closely related clustering problems, Min Sum k-Clustering (MSkC) and Balanced k-Median (BkM). In Min Sum k-clustering, 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 k-Median 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
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial 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.