Cohen-Addad, Vincent ; Gupta, Anupam ; Kumar, Amit ; Lee, Euiwoong ; Li, Jason (2019) Tight FPT Approximations for k-Median and k-Means In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 8-12 July 2019, Patras, Greece.
Full text not available from this repository.
Official URL: http://drops.dagstuhl.de/opus/volltexte/2019/10618
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+epsilon) and (1+8/e+epsilon) 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.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. |
| Keywords: | Approximation Algorithms; Fixed-Parameter Tractability; k-Median, k-Means; Clustering; Core-Sets. |
| ID Code: | 123501 |
| Deposited On: | 29 Sep 2021 07:55 |
| Last Modified: | 29 Sep 2021 07:55 |
Repository Staff Only: item control page
