This paper presents a fast and simple new 2-approximation algorithm for minimum weighted vertex cover. The unweighted version of this algorithm is equivalent to a well-known greedy maximal independent set algorithm. We prove that this independent set algorithm produces a 2-approximate vertex cover, and we provide a principled new way to generalize it to node-weighted graphs. Our analysis is inspired by connections to a clustering objective called correlation clustering. To demonstrate the relationship between these problems, we show how a simple Pivot algorithm for correlation clustering implicitly approximates a special type of hypergraph vertex cover problem. Finally, we use implicit implementations of this maximal independent set algorithm to develop fast and simple 2-approximation algorithms for certain edge-deletion problems that can be reduced to vertex cover in an approximation preserving way.
翻译:本文为最小加权顶层覆盖提供了一个快速和简单的新 2 近似值新算法。 未加权的这一算法版本相当于众所周知的贪婪最大独立套算法。 我们证明这一独立套算法产生了2- 近似顶层覆盖, 我们提供了一种有原则的新方法, 将其概括为节点加权图。 我们的分析来源于与一个称为相关组合的集群目标的连接。 为了显示这些问题之间的关系, 我们展示了一种简单的关联组合参数算法如何暗含着一种特殊的高光学顶层覆盖问题。 最后, 我们用隐含的这个最大独立算法来发展快速和简单的2 近似值顶部覆盖值算法, 以近似保存方式将某些边缘偏移问题降低为顶层覆盖。