Abstract
The Metric kmedian problem over a metric space (š³, d) is defined as follows: given a set L ā š³ of facility locations and a set C ā š³ of clients, open a set F ā L of k facilities such that the total service cost, defined as Ī¦(F, C) := ā_{x ā C} min_{f ā F} d(x, f), is minimised. The metric kmeans problem is defined similarly using squared distances (i.e., dĀ²(., .) instead of d(., .)). In many applications there are additional constraints that any solution needs to satisfy. For example, to balance the load among the facilities in resource allocation problems, a capacity u is imposed on every facility. That is, no more than u clients can be assigned to any facility. This problem is known as the capacitated kmeans/kmedian problem. Likewise, various other applications have different constraints, which give rise to different constrained versions of the problem such as rgather, faulttolerant, outlier kmeans/kmedian problem. Surprisingly, for many of these constrained problems, no constantapproximation algorithm is known. Moreover, the unconstrained problem itself is known [Marek Adamczyk et al., 2019] to be W[2]hard when parameterized by k. We give FPT algorithms with constant approximation guarantee for a range of constrained kmedian/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu [Ding and Xu, 2015] that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a (3+Īµ)approximation and (9+Īµ)approximation for the constrained versions of the kmedian and kmeans problem respectively in FPT time. In many practical settings of the kmedian/means problem, one is allowed to open a facility at any client location, i.e., C ā L. For this special case, our algorithm gives a (2+Īµ)approximation and (4+Īµ)approximation for the constrained versions of kmedian and kmeans problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constantpass logspace streaming algorithm. In particular, here are some of the main highlights of this work:
1) For the uniform capacitated kmedian/means problems our results matches previously known results of Addad et al. [Vincent CohenAddad and Jason Li, 2019].
2) For the rgather kmedian/means problem (clustering with lower bound on the size of clusters), our FPT approximation bounds are better than what was previously known.
3) Our approximation bounds for the faulttolerant, outlier, and uncertain versions is better than all previously known results, albeit in FPT time.
4) For certain constrained settings such as chromatic, ldiversity, and semisupervised kmedian/means, we obtain the first constant factor approximation algorithms to the best of our knowledge.
5) Since our algorithms are based on a simple sampling based approach, we also obtain constantpass logspace streaming algorithms for most of the abovementioned problems.
BibTeX  Entry
@InProceedings{goyal_et_al:LIPIcs:2020:13317,
author = {Dishant Goyal and Ragesh Jaiswal and Amit Kumar},
title = {{FPT Approximation for Constrained Metric kMedian/Means}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {14:114:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13317},
URN = {urn:nbn:de:0030drops133170},
doi = {10.4230/LIPIcs.IPEC.2020.14},
annote = {Keywords: kmeans, kmedian, approximation algorithms, parameterised algorithms}
}
Keywords: 

kmeans, kmedian, approximation algorithms, parameterised algorithms 
Collection: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 