On the Fixed-Parameter Tractability of Capacitated Clustering

Vincent Cohen-Addad, Jason Li

We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best…