首页> 外文期刊>Journal of Computer and System Sciences >A Constant-Factor Approximation Algorithm for the k- MST Problem
【24h】

A Constant-Factor Approximation Algorithm for the k- MST Problem

机译:k-MST问题的常数因子近似算法

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

摘要

Given an undirected graph with nonnegative edge costs and an integer k, the k- MST problem is that of finding a tree of minimum cost on k nodes. This problem is known to be NP-hard. We present a simple approximation algorithm that finds a solution whose cost is less than 17 times the cost of the optimum. This improves upon previous perfor- mance ratios for this problem -- O(sq root K) due to Ravi et al., O(log~2 k) due to Awerbuch et al., and the previous best bound of O(log k ) due to Rajagopalan and Vazirani. Given any 0 < a < 1, we first present a bicriteria approximation algorithm that outputs a tree on p ≥ ak vertices of total cost at most 2pL (1 - a) k, where L is the cost of the optimal k-MST. The running time of the algorithm is O(n~2 log~2 n ) on an n- node graph. We then show how to use this algorithm to derive a constant factor approximation algorithm for the k-MST problem. The main subroutine in our algorithm is an approximation algorithm of Goemans and Williamson for the prize--collecting Steiner tree problem.
机译:给定具有非负边缘成本和整数k的无向图,则k-MST问题是在k个节点上找到最小成本的树。已知此问题是NP难题。我们提出一种简单的近似算法,该算法可以找到成本低于最佳成本17倍的解决方案。相对于此问题,以前的性能比率得到了改善-Ravi等人提出了O(sq根K),Awerbuch等人提出了O(log〜2 k),以及O(log k )由于Rajagopalan和Vazirani。给定任何0 <1,我们首先提出一种双标准近似算法,该算法在总成本最多2pL(1- a)k的p≥ak个顶点上输出树,其中L是最优k-MST的成本。该算法的运行时间在n节点图上为O(n〜2 log〜2 n)。然后,我们展示如何使用此算法来推导k-MST问题的常数因子近似算法。该算法的主要子例程是Goemans和Williamson的近似算法,用于奖品收集Steiner树问题。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号