...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs
【24h】

Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs

机译：二分钟中最大K-顶点盖的纯组合近似算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the polynomial time approximation of the NP-hard MAX k-VERTEX COVER problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2/3 and 34/47 approximate to 0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1-1/e) approximate to 0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for MAX k-VERTEX COVEr compete with linear programming ones? (C) 2017 Elsevier B.V. All rights reserved.
机译：研究了二部图中NP-难最大k-顶点覆盖问题的多项式时间逼近，提出了纯组合逼近算法。本文的主要结果是一个简单的组合算法和对其近似保证的计算机辅助分析，有力地证明了所获得的最差近似比在0.821以下。我们还研究了两种更简单的策略，它们的可证明近似比分别为2/3和34/47，接近于0.72，这两种策略已经击败了唯一一种已知的算法，即贪婪方法，它保证了近似比（1-1/e）接近于0.632。我们的主要动机是在以下问题中给出满意的答案：最大k顶点覆盖的组合方法在多大程度上与线性规划方法相竞争？（C） 2017爱思唯尔B.V.版权所有。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号