图割和聚类中的局部保证

Apr, 2017

Local Guarantees in Graph Cuts and Clustering

Moses Charikar, Neha Gupta, Roy Schwartz

TL;DR本研究提出了一种新的 min-max 图割算法 ——Min Max s-t Cut，同时探讨了基于局部目标的方法，针对最大不同数，给出了最大总权重的最小化问题的一个 O (√n) 近似算法，局部无序最小化问题的一个简单的 7 - 近似算法，以及最小总权重的最大化问题的一个更好的 1/(2+ε) 近似算法。

Abstract

correlation clustering is an elegant model that captures fundamental graph cut problems such as Min $s-t$ Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled $+$ or $-$ and the goal is to produce a clustering

correlation clustering graph cut problems min-max graph cut problems local objectives approximation

发现论文，激发创造

多割最小最大相关聚类

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

Jun, 2019

定数个簇的相关聚类

研究聚类分析中的一种新方法 —— 相关聚类或定性信息聚类，探讨了最大化协议的问题和最小化分歧的问题，重点研究了聚类数为常数 k 的情况，发现该问题具有多项式时间近似解，为解决最小化分歧问题做了大量的技术工作。

Apr, 2005

局部有界误差相关聚类和双聚类

提出了一个新的框架，使得在完全图上具有带权边标识的相关性聚类问题得以处理，该算法可近似求解多种目标函数下的离散聚类问题。

Jun, 2015

最小最大相关聚类的 4 近似算法

我们介绍了一种用于最小最大相关聚类问题的下界技术，并基于此技术提出了一种完全图的组合 4 近似算法。我们通过贪婪连接启发式算法扩展了这个算法，并在几个基准数据集上实证表明它提高了解决方案的质量和运行时间，改进了现有的技术水平。

Oct, 2023

使用同簇查询的近似相关聚类

该研究介绍了一种半监督聚类框架及其在相关性聚类问题中的应用，提出了一种有效的近似算法，并给出了同类查询数量的上下界。

Dec, 2017

具有不对称分类误差的本地相关聚类

研究了具有加权图的相关聚类问题，在此问题下，通过加权边标记为相似或不相似，通过最小化不同意向量的 l_p 规范的目标函数，提供了一个近似算法。

Aug, 2021

潜在的随机步骤作为最大割、最小割和更多的松弛

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

Aug, 2023

具有不对称分类误差的相关聚类

本文研究了相关聚类问题在每个相似边和不相似边权重符合一定假设下的近似算法，并给出了此问题渐近匹配的线性规划完整性间隙。

Aug, 2021

高效查询相关聚类

本文主要研究了查询效率，使用类似于计算距离的相似度度量，通过提出新的算法实现了更加高效的相关聚类，能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果，并且针对算法进行了实验研究。

Feb, 2020

通过强三元闭包标记的相关聚类：快速近似算法和实用下界

本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

Nov, 2021