Abstract
We consider the MinSum kClustering (kMSC) problem. Given a set of points in a metric which is represented by an edgeweighted graph G = (V, E) and a parameter k, the goal is to partition the points V into k clusters such that the sum of distances between all pairs of the points within the same cluster is minimized.
The kMSC problem is known to be APXhard on general metrics. The best known approximation algorithms for the problem obtained by Behsaz, Friggstad, Salavatipour and Sivakumar [Algorithmica 2019] achieve an approximation ratio of O(log V) in polynomial time for general metrics and an approximation ratio 2+ε in quasipolynomial time for metrics with bounded doubling dimension. No approximation schemes for kMSC (when k is part of the input) is known for any nontrivial metrics prior to our work. In fact, most of the previous works rely on the simple fact that there is a 2approximate reduction from kMSC to the balanced kmedian problem and design approximation algorithms for the latter to obtain an approximation for kMSC.
In this paper, we obtain the first QuasiPolynomial Time Approximation Schemes (QPTAS) for the problem on metrics induced by graphs of bounded treewidth, graphs of bounded highway dimension, graphs of bounded doubling dimensions (including fixed dimensional Euclidean metrics), and planar and minorfree graphs. We bypass the barrier of 2 for kMSC by introducing a new clustering problem, which we call minhub clustering, which is a generalization of balanced kmedian and is a trade off between centerbased clustering problems (such as balanced kmedian) and pairwise clustering (such as MinSum kclustering). We then show how one can find approximation schemes for Minhub clustering on certain classes of metrics.
BibTeX  Entry
@InProceedings{naderi_et_al:LIPIcs.ESA.2023.84,
author = {Naderi, Ismail and Rezapour, Mohsen and Salavatipour, Mohammad R.},
title = {{Approximation Schemes for MinSum kClustering}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {84:184:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18737},
URN = {urn:nbn:de:0030drops187379},
doi = {10.4230/LIPIcs.ESA.2023.84},
annote = {Keywords: Approximation Algorithms, Clustering, Dynamic Programming}
}
Keywords: 

Approximation Algorithms, Clustering, Dynamic Programming 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 