correlation clustering is a fundamental combinatorial optimization problem
arising in many contexts and applications that has been the subject of dozens
of papers in the literature. In this problem we are given a general weighted
graph where each edge is labeled positive or negative. T
我们在这篇论文中建立了多层相关聚类，这是对相关聚类（Bansal 等人，FOCS'02）在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法（其中 L 是层数），然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法，该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。