Tight FPT approximation for constrained k-center and k-supplier

In this work, we study a range of constrained versions of the k-supplier and k-center problems. In the classical (unconstrained) k-supplier problem, we are given a set of clients C in a metric space chi, with distance function d(., .). We are also given a set of feasible facility locations L subset of chi. The goal is to open a set F of k facilities in L to minimize the maximum distance of any client to the closest open facility, i.e., minimize, cost(F, C) equivalent to max(jC) {d(F, j)}, where d(F, j) is the distance of client j to the closest facility in F. The k-center problem is a special case of the k-supplier problem where L = C. We study various constrained versions of the k-supplier problem such as: capacitated, fault-tolerant, B-diversity, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [Algorithmica 2020] in the context of the k-median and k-means objectives. We extend this framework to the k-supplier and k-center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k-supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, B -diversity, and fair k-supplier problems, with and without outliers. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter k is a small number in many real clustering scenarios. We obtain the following results: center dot We give 3 and 2 approximation algorithms for the constrained k-supplier and k-center problems, respectively, with FPT running time k(O(k)) center dot n(O(1)), where n = |C U L|. Moreover, these approximation guarantees are tight; that is, for any constant epsilon > 0, no algorithm can achieve (3-epsilon) and (2-epsilon) approximation guarantees for the constrained k-supplier and k-center problems in FPT time, assuming FPT not equal W[2]. center dot We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k-supplier and k-center problems, respectively, with FPT running time (k + m)(O(k)) center dot n(O(1)), where n = |C U L| and m is the number of outliers. center dot Our techniques generalise for distance function d(., .)(z). That is, for any positive real number z, if the cost of a client is defined by d(., .)(z) instead of d(., .), then our algorithm gives 3(z) and 2(z) approximation guarantees for the constrained k-supplier and k-center problems, respectively.