# Parameterized Complexity of Categorical Clustering with Size Constraints

arXiv: https://arxiv.org/abs/2104.07974 · HTML: https://mlsanity.com/paper/2104.07974/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [Categorical data clustering: 25 years beyond K-modes](https://mlsanity.com/paper/2408.17244/) (2024)

## Abstract (arXiv)

In the Categorical Clustering problem, we are given a set of vectors (matrix) A=a1,ldots,an over Sigmam, where Sigma 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. That is, we seek a partition I1,ldots,Ik of 1,ldots,n and vectors c1,ldots,ck∈Sigmam such that sumi=1ksumj∈ Iidh(ci,aj)≤ B, where dH(a,b) is the Hamming distance between vectors a and b. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable (for binary case Sigma=0,1) by giving an algorithm that solves the problem in time 2O(Blog B) (mn)O(1). We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters should satisfy certain constraints. More precisely, in Capacitated Clustering, in addition, we are given two non-negative integers p and q, and seek a clustering with p≤ |Ii|≤ q for all i∈1,ldots,k. Our main theorem is that Capacitated Clustering is solvable in time 2O(Blog B)|Sigma|B(mn)O(1). The theorem not only extends the previous algorithmic results to a significantly more general model, it also implies algorithms for several other variants of Categorical Clustering with constraints on cluster sizes.