TY - GEN
T1 - Tight FPT approximations for k-median and K-means
AU - Cohen-Addad, Vincent
AU - Gupta, Anupam
AU - Kumar, Amit
AU - Lee, Euiwoong
AU - Li, Jason
N1 - Publisher Copyright:
© Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li; licensed under Creative Commons License CC-BY
PY - 2019/7/1
Y1 - 2019/7/1
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Clustering
KW - Core-sets
KW - Fixed-parameter tractability
KW - K-means
KW - K-median
UR - http://www.scopus.com/inward/record.url?scp=85069212610&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069212610&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2019.42
DO - 10.4230/LIPIcs.ICALP.2019.42
M3 - Conference contribution
AN - SCOPUS:85069212610
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
A2 - Baier, Christel
A2 - Chatzigiannakis, Ioannis
A2 - Flocchini, Paola
A2 - Leonardi, Stefano
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Y2 - 9 July 2019 through 12 July 2019
ER -