研究如何高效公平地对离散向量聚类，发现传统方法失效并提出新解法。
Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
- 将公平聚类转化为修改矩阵中颜色平衡行的组合问题
- 证明在严格公平约束下无法用参数算法高效求解
- 提出三种新策略绕过计算瓶颈，适合理论与优化研究者
我们研究计算离散向量公平均值聚类的计算问题，该问题可等价表述为：通过最多更改 $k$ 个值，将一个带色矩阵编辑为具有较少不同颜色平衡行的形式。尽管在无公平性约束和有公平性约束下均为 NP-hard，前者已知存在固定参数算法。作为首个贡献，我们排除了在高度受限的公平均值聚类实例中存在类似算法的可能性。随后，我们建立该问题的完整复杂性图景，并获得三类可 tractability 结果：施加额外实例约束、采用固定参数近似，或使用针对树状矩阵的替代参数化方式。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。