Tight FPT approximations for k-median and K-means

Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We investigate the fine-grained complexity of approximating the classical k-Median/k-Means clustering problems in general metric spaces. We show how to improve the approximation factors to (1 + 2/e + ε) and (1 + 8/e + ε) respectively, using algorithms that run in fixed-parameter time. Moreover, we show that we cannot do better in FPT time, modulo recent complexity-theoretic conjectures.

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Country/TerritoryGreece
CityPatras
Period7/9/197/12/19

Keywords

  • Approximation algorithms
  • Clustering
  • Core-sets
  • Fixed-parameter tractability
  • K-means
  • K-median

ASJC Scopus subject areas

  • Software

Cite this