License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.14
URN: urn:nbn:de:0030-drops-115761
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11576/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Simonov, Kirill
Parameterized k-Clustering: Tractability Island
Abstract
In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} sum_{x in C_i} |x-c_i|_p^p <= D, where |*|_p is the Minkowski (L_p) norm of order p. For p=1, k-Clustering is the well-known k-Median. For p=2, the case of the Euclidean distance, k-Clustering is k-Means. We study k-Clustering from the perspective of parameterized complexity. The problem is known to be NP-hard for k=2 and it is also NP-hard for d=2. It is a long-standing open question, whether the problem is fixed-parameter tractable (FPT) for the combined parameter d+k. In this paper, we focus on the parameterization by D. We complement the known negative results by showing that for p=0 and p=infty, k-Clustering is W1-hard when parameterized by D. Interestingly, the complexity landscape of the problem appears to be more intricate than expected. We discover a tractability island of k-Clustering: for every p in (0,1], k-Clustering is solvable in time 2^O(D log D) (nd)^O(1).
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2019:11576,
author = {Fedor V. Fomin and Petr A. Golovach and Kirill Simonov},
title = {{Parameterized k-Clustering: Tractability Island}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-131-3},
ISSN = {1868-8969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11576},
URN = {urn:nbn:de:0030-drops-115761},
doi = {10.4230/LIPIcs.FSTTCS.2019.14},
annote = {Keywords: clustering, parameterized complexity, k-means, k-median}
}
|
Keywords: |
|
clustering, parameterized complexity, k-means, k-median |
|
Collection: |
|
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.12.2019 |
