论文标题
相关聚类的四种算法：调查
Four Algorithms for Correlation Clustering: A Survey
论文作者
论文摘要
在相关聚类问题中，我们为我们提供了一组具有成对相似性信息的对象。我们的目的是将这些对象划分为尽可能紧密匹配此信息的群集。更具体地说，成对信息是作为加权图$ g $给出的，其边缘被标记为``类似的''或``不同''二进制分类器。目的是产生聚类，以最大程度地减少``分歧''的重量：群集内的类似边缘和相似边缘的重量总和群集中。在此博览会中，我们关注$ g $完全且未加权的情况。我们探索了四个近似算法的相关性问题。 $ 17429- $ $近似算法，Bansal，Blum和Chawla，（ii）Charikar，Guruswami，Guruswami和Wirth（iii）的$ 4- $近似算法（III）$ 3- $ $ $近似算法，Ailon，Charikar和Newman，Newman和Newman（IV）$ 2.06- $ 2.06- chare， Schramm和Yaroslavtsev。
In the Correlation Clustering problem, we are given a set of objects with pairwise similarity information. Our aim is to partition these objects into clusters that match this information as closely as possible. More specifically, the pairwise information is given as a weighted graph $G$ with its edges labelled as ``similar" or ``dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of ``disagreements": the sum of the weights of similar edges across clusters and dissimilar edges within clusters. In this exposition we focus on the case when $G$ is complete and unweighted. We explore four approximation algorithms for the Correlation Clustering problem under this assumption. In particular, we describe the following algorithms: (i) the $17429-$approximation algorithm by Bansal, Blum, and Chawla, (ii) the $4-$approximation algorithm by Charikar, Guruswami, and Wirth (iii) the $3-$approximation algorithm by Ailon, Charikar, and Newman (iv) the $2.06-$approximation algorithm by Chawla, Makarychev, Schramm, and Yaroslavtsev.
