Search

In the Categorical Clustering problem, we are given a set of vectors (matrix) A = { a 1 , ... , a n } over Σ m , where Σ is a finite alphabet, and integers k and B. The task is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable for the binary case Σ = { 0 , 1 }. We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters are lower and upper bounded by integer parameters p and q , respectively. Our main theorem is that the problem is solvable in time 2 O (B log ⁡ B) | Σ | B ⋅ (m n) O (1). [ABSTRACT FROM AUTHOR]