研究了具有加权图的相关聚类问题,在此问题下,通过加权边标记为相似或不相似,通过最小化不同意向量的 l_p 规范的目标函数,提供了一个近似算法。
Aug, 2021
提出了一个新的框架,使得在完全图上具有带权边标识的相关性聚类问题得以处理,该算法可近似求解多种目标函数下的离散聚类问题。
Jun, 2015
本文主要研究了查询效率,使用类似于计算距离的相似度度量,通过提出新的算法实现了更加高效的相关聚类,能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果,并且针对算法进行了实验研究。
Feb, 2020
该研究介绍了一种半监督聚类框架及其在相关性聚类问题中的应用,提出了一种有效的近似算法,并给出了同类查询数量的上下界。
Dec, 2017
本文提供了第一个问题的非平凡近似算法,来解决最小化每个子群组的最大不一致数的最小化最大相关聚类问题,并对 multicut 问题得出了相应的结果。
Jun, 2019
我们在这篇论文中建立了多层相关聚类,这是对相关聚类(Bansal 等人,FOCS'02)在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法(其中 L 是层数),然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法,该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。
Apr, 2024
本研究提出了更快的近似算法,避免了其最佳逼近算法所依赖的不切实际的线性规划放宽,为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术,包括聚簇删除的第一个组合逼近算法,实际应用中,我们的算法产生了近乎与质量最佳算法相匹配的近似解,同时适用于数量级更大的问题。
Nov, 2021
本文介绍了在具有聚类大小限制以及边权重正负约束的图上的相关聚类问题。该研究提出了在边权重值为常数近似保证的情况下,解决带有聚类大小限制的相关聚类问题的方法。
Nov, 2014
本研究提出了一种新的 min-max 图割算法 ——Min Max s-t Cut,同时探讨了基于局部目标的方法,针对最大不同数,给出了最大总权重的最小化问题的一个 O (√n) 近似算法,局部无序最小化问题的一个简单的 7 - 近似算法,以及最小总权重的最大化问题的一个更好的 1/(2+ε) 近似算法。
Apr, 2017
本文研究动态数据流模型下相关聚类问题,结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法,解决了自然问题。
Dec, 2018