本文提供了第一个问题的非平凡近似算法，来解决最小化每个子群组的最大不一致数的最小化最大相关聚类问题，并对 multicut 问题得出了相应的结果。

Jun, 2019

本文提出了一种基于分割二分图的新型数据聚类方法，旨在最小化未匹配的顶点之间的边权重总和，通过边权重矩阵的奇异值分解来近似解决这个最小化问题并且在文档聚类问题上取得了显著的效果。

Aug, 2001

基于非负矩阵分解的概率模型统一了节点聚类和图简化，提供了建模任意图结构的框架。通过将硬聚类放松为软聚类，我们的算法将潜在的困难聚类问题转化为易处理的问题。

Aug, 2023

提出一种新算法 - Laplacian K-modes 聚类算法，它融合了聚类中三种不同的思想：K-means 中的隐式分配变量，mean-shift 中的密度估计，和图拉普拉斯正则化效应中的近邻点相似性分配，该算法可以解决难以聚类的问题，同时提供了一个预测新点的软分配映射。

Jun, 2014

本文提出了针对多个保护类的公平聚类方法，并且提出了一种松散的公平概念，在这种概念下，可以对所有经典聚类目标进行双标准常数因子近似，这是通过将任意现有不公平的（整数）解和公平的（分数）线性规划解结合起来实现的。

Nov, 2018

我们提出了一种定制的分支限界算法来解决 $k$-densest-disjoint biclique 问题，通过同时聚类数据矩阵的行和列，找到给定加权完全二分图的 $k$ 个不相交的完全二分子图（称为 bicliques），使它们的密度之和最大化。

Mar, 2024

通过一种新的方法，我们明确和形式上展示了 center-based 方法在某些应用程序中的优越性。

Sep, 2011

本文提出了一种紧密的连续松弛方法用于解决图的平衡 k 切问题，以优化标准的归一化切，通过求解难以优化的比例和问题，进一步优化算法表现，实验比较证明该方法胜过现有的全部方法。

May, 2015

本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。

Feb, 2020

本文提出了一种针对图中任意形状节点簇的差分隐私聚类算法，该算法仅使用在权重差分隐私约束下释放的近似最小生成树作为输入，并通过最优剪切方法从中成功恢复底层的非凸聚类分区。与现有方法不同，我们的算法在理论上得到了很好的支持，并且实验证实了我们的理论发现。

Mar, 2018