论文标题
恒定回合中的几乎3个同一相关聚类
Almost 3-Approximate Correlation Clustering in Constant Rounds
论文作者
论文摘要
我们研究用于相关聚类的平行算法。 $ n $对象之间的每对被标记为“类似”或“不同”。目的是将对象分配为任意的许多集群，同时最大程度地减少与标签的分歧数量。 我们的主要结果是一种算法，即对于任何$ε> 0 $都可以在$ O（1/ε）$ rounds中获得$（3+ε）$ - 近似值（例如大量并行计算，本地和半流）。这是关于平行相关聚类的丰富文献的最终结论。一方面，对于组合算法，近似值（几乎）（几乎）与3的天然屏障相匹配。另一方面，算法的圆形复杂性本质上是恒定的。 为了实现此结果，我们引入了一个简单的$ O（1/ε）$ - 圆形并行算法。我们的主要结果是对该算法进行分析，表明它达到了$（3+ε）$ - 近似。我们的分析借鉴了与均匀时间算法的新连接。具体而言，它建立在Yoshida，Yamamoto和Ito [Stoc'09]方面的工作，以界定贪婪最大独立集的“查询复杂性”。据我们所知，这是该方法在分析任何算法的近似值时的第一个应用。
We study parallel algorithms for correlation clustering. Each pair among $n$ objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $ε> 0$ obtains a $(3+ε)$-approximation in $O(1/ε)$ rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm's round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/ε)$-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a $(3+ε)$-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [STOC'09] on bounding the "query complexity" of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm.
