Parameterized k-Clustering: Tractability island.

In k -Clustering we are given a multiset of n vectors X ⊂ 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 ∑ i = 1 k min c i ∈ R d ⁡ ∑ x ∈ C i ‖ x − c i ‖ p p ≤ D , where ‖ ⋅ ‖ p is the L p -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 2 O (D log ⁡ D) (n d) O (1). [ABSTRACT FROM AUTHOR]