Parameterized k-Clustering: Tractability island

摘要

In k-Clustering we are given a multiset of n vectors X⊂Zd and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C1,…,Ck such that the cost∑i=1kminci∈Rd⁡∑x∈Ci‖x−ci‖pp≤D, where ‖⋅‖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=∞, k-Clustering is W[1]-hard when parameterized by D. Interestingly, we discover a tractability island of k-Clustering: for every p∈(0,1], k-Clustering is solvable in time 2O(Dlog⁡D)(nd)O(1).