首页> 外文期刊>Algorithmica >A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses
【24h】

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

机译:部分顶点覆盖的原始对偶逼近算法:使受过教育的猜测

获取原文
获取原文并翻译 | 示例

摘要

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R +, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k u . A solution consists of a function x:V→ℕ0 and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x u k u . Our objective is to find a cover that minimizes ∑ v∈V x v w v . This is the first 2-approximation for the problem and also runs in O(nlog n+m) time.
机译:我们研究部分顶点覆盖问题。给定一个图G =(V,E),权重函数w:V→R + 和一个整数s,我们的目标是通过选择一组顶点来覆盖除s以外的所有边最小重量。这个问题显然是NP难的,因为它推广了众所周知的顶点覆盖问题。我们提供了以O(nlog n + m)时间运行的原始对偶2逼近算法。与以前已知的最快算法相比,这代表了运行时间的改进。我们的技术也可以用于对问题的更一般版本进行2逼近。在部分电容的顶点覆盖问题中,每个顶点u都具有容量k u 。一个解决方案由一个函数x:V→ℕ 0 和除s以外的所有边的方向组成,这样,朝向顶点u的边数最多为x u k u 。我们的目标是找到一个使∑ v∈V x v w v 最小的封面。这是问题的第一个2逼近,并且以O(nlog n + m)时间运行。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号