# Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 3 Dec 2025.

## Builds on (most cited first, 6 of 6)

- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Parameterized Low-Rank Binary Matrix Approximation](https://mlsanity.com/paper/1803.06102/) (2018)
- [Approximation Schemes for Low-Rank Binary Matrix Approximation Problems](https://mlsanity.com/paper/1807.07156/) (2018)
- [k-Means Clustering of Lines for Big Data](https://mlsanity.com/paper/1903.06904/) (2019)
- [The Complexity of Binary Matrix Completion Under Diameter Constraints](https://mlsanity.com/paper/2002.05068/) (2020)

## Abstract (arXiv)

We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few distinct color-balanced rows by changing at most k values. While NP-hard in both the fairness-oblivious and the fair settings, the problem is well-known to admit a fixed-parameter algorithm in the former ``vanilla'' setting. As our first contribution, we exclude an analogous algorithm even for highly restricted fair means clustering instances. We then proceed to obtain a full complexity landscape of the problem, and establish tractability results which capture three means of circumventing our obtained lower bound: placing additional constraints on the problem instances, fixed-parameter approximation, or using an alternative parameterization targeting tree-like matrices.