Fomin, Fedor V. ;
Golovach, Petr A. ;
Simonov, Kirill
Parameterized kClustering: Tractability Island
Abstract
In kClustering 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} xc_i_p^p <= D, where *_p is the Minkowski (L_p) norm of order p. For p=1, kClustering is the wellknown kMedian. For p=2, the case of the Euclidean distance, kClustering is kMeans. We study kClustering from the perspective of parameterized complexity. The problem is known to be NPhard for k=2 and it is also NPhard for d=2. It is a longstanding open question, whether the problem is fixedparameter 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, kClustering is W1hard when parameterized by D. Interestingly, the complexity landscape of the problem appears to be more intricate than expected. We discover a tractability island of kClustering: for every p in (0,1], kClustering 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 kClustering: Tractability Island}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {14:114:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771313},
ISSN = {18688969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11576},
URN = {urn:nbn:de:0030drops115761},
doi = {10.4230/LIPIcs.FSTTCS.2019.14},
annote = {Keywords: clustering, parameterized complexity, kmeans, kmedian}
}
04.12.2019
Keywords: 

clustering, parameterized complexity, kmeans, kmedian 
Seminar: 

39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 