Parameterized k-Clustering: Tractability island

In k-CLUSTERING we are given a multiset of n vectors X subset of 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 Sigma(k)(i=1) min (ci is an element of Rd) Sigma(x is an element of ci)parallel to x-c(i)parallel to(p)(p) <= D where parallel to center dot parallel to p is the Lp-norm. For p = 2, 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 also 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 = infinity, k-CLUSTERING is W[1]-hard when parameterized by D. Interestingly, we discover a tractability island of k-CLUSTERING: for every p is an element of (0, 1], k-CLUSTERING is solvable in time 2(O(D log D))(nd)(O(1)). (C) 2020 The Author(s). Published by Elsevier Inc.