- 126 views
- 151 downloads
Approximation Schemas for the Min Sum k-Clustering Problem
-
- Author / Creator
- Naderi Beni, Ismail
-
In this thesis, we present Approximation Schemes for the Min Sum k Clustering problem on a number of classes of graph metrics. In Min Sum k Clustering problem introduced by Sahni and Gonzalez [22] in 1976, given a graph G(V, E) with metric edge costs and parameter k, we are asked to partition V (i.e. assume all V must be clustered) into clusters C1, C2, · · · , Ck such that the sum of pairwise distances of points in the same cluster is minimized. This is a generalization of k-median clustering with avoiding unbalanced cluster sizes. The best known algorithm for Min Sum k Clustering by Behsaz, Friggstad, Salavatipour and Sivakumar [6] on metric spaces is an O(log n) approximation algorithm. Even for the case of trees, the best approximation factor given by the same authors is 2 + ε . Cohen-Addad, Karthik, and Lee [11] proved that min sum k clustering is APX-Hard on Metric spaces, i.e. there isn’t any PTAS unless P=NP. In this work, we will make an improvement on this problem by presenting the first Quasi Polynomial Time Approximation Schemes for several graph metrics: graphs of bounded treewidth, graphs of bounded highway dimension, and graphs of bounded doubling dimensions.
-
- Graduation date
- Spring 2023
-
- 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 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.