article · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019

On the Fixed-Parameter Tractability of Capacitated Clustering

Cited by 12Open access

Abstract

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 known approximation bound for high dimensional Euclidean space and general metric space is Theta(log k) and it remains a major open problem whether a constant factor exists.\nWe show that there exists a (3+epsilon)-approximation algorithm for the capacitated k-median and a (9+epsilon)-approximation algorithm for the capacitated k-means problem in general metric spaces whose running times are f(epsilon,k) n^{O(1)}. For Euclidean inputs of arbitrary dimension, we give a (1+epsilon)-approximation algorithm for both problems with a similar running time. This is a significant improvement over the (7+epsilon)-approximation of Adamczyk et al. for k-median in general metric spaces and the (69+epsilon)-approximation of Xu et al. for Euclidean k-means.

Cite this paper

APA 7

Cohen-Addad, V., & Li, J. (2019). On the Fixed-Parameter Tractability of Capacitated Clustering. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.icalp.2019.41

MLA 9

Cohen-Addad, Vincent, and Jason Li. “On the Fixed-Parameter Tractability of Capacitated Clustering.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 2019, https://doi.org/10.4230/lipics.icalp.2019.41.

Chicago

Cohen-Addad, Vincent, and Jason Li. 2019. “On the Fixed-Parameter Tractability of Capacitated Clustering.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.icalp.2019.41.

Harvard

Cohen-Addad, V. and Li, J. (2019) ‘On the Fixed-Parameter Tractability of Capacitated Clustering’, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). Available at: https://doi.org/10.4230/lipics.icalp.2019.41.

BibTeX

@article{cohenaddad2019fixed,
  title = {{On the Fixed-Parameter Tractability of Capacitated Clustering}},
  author = {Cohen-Addad, Vincent and Li, Jason},
  journal = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2019},
  doi = {10.4230/lipics.icalp.2019.41}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.