On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm k-clustering problems, parameterized by the number k of open facilities. For the capacitated setting, we give a tight (3+ϵ)-approximation for the general-norm capacitated k-clustering problem in FPT-time parameterized by k and ϵ. Prior to our work, such a result was only known for the capacitated k-median problem [25]. As a special case, our result yields an FPT-time 3-approximation for capacitated k-center. The problem has not been studied in the FPT-time setting, with the previous best known polynomial-time approximation ratio being 9 [6]. In the uncapacitated setting, we consider the top-cn norm k-clustering problem, where the goal of the problem is to minimize the top-cn norm of the connection distance vector. Our main result is a tight (Formula presented)-approximation algorithm for the problem with (Formula presented). (For the case c ≤ ¹_e, there is a simple tight (3 + ϵ)-approximation.) Our framework can be easily extended to give a tight (Formula presented)-bi-criteria approximation for the (k-center, k-median) problem in FPT time, improving the previous best polynomial-time (4, 8) guarantee [5]. All results are based on a unified framework: computing a (1 + ϵ)-approximate solution using (Formula presented) facilities S via LP rounding, sampling a few client representatives R based on the solution S, guessing a few pivots from S ∪ R and some radius information on the pivots, and solving the problem using the guesses. We believe this framework can lead to further results on k-clustering problems.