论文标题
生长一个随机的最大独立集产生2个值得注意的顶点盖
Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
论文作者
论文摘要
本文介绍了一种快速，简单的新2-辅助算法，用于最小加权顶点盖。该算法的未加权版本相当于众所周知的贪婪最大独立集算法。我们证明，这种独立的集合算法会产生2个值得注意的顶点盖，并且我们提供了一种将其推广到节点加权图的新方法。我们的分析灵感来自与称为相关聚类的聚类目标的连接。为了证明这些问题之间的关系，我们展示了一个简单的枢轴算法用于相关聚类的群集隐式近似于特殊类型的超透明顶点覆盖问题。最后，我们使用此最大独立集算法的隐式实现来开发快速，简单的2-辅助算法，以解决某些边缘缺失问题，这些问题可以以近似值保留方式将其简化为顶点覆盖。
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.
