...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
【24h】

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks

机译：用于集合多重覆盖问题的随机近似算法及其在蛋白质和基因网络逆向工程中的应用

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

摘要

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial version of the problem and observe that this is "equivalent" to the set multicover problem when the "coverage" factor k is a function of the number of elements it of the universe. An important special case for our application is the case in which k = n - 1. We observe that the standard greedy algorithm produces an approximation ratio of Omega(log n) even if k is "large" i.e k = n - c for some constant c > 0. Let 1 < a < n denote the maximum number of elements in any given set in our set multicover problem. Then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio E vertical bar r(a, k)vertical bar that is an increasing function of a/k. The behavior of E vertical bar r(a, k)vertical bar is roughly as follows: it is about In(a/k) when a/k is at least about e(2) approximate to 7.39, and for smaller values of a/k it decreases towards 1 as a linear function of root a/k with lim(a/k -> 0) E vertical bar r(a, k)vertical bar = 1. Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity beta followed by a greedy solution for the remaining problem. We also comment about the impossibility of a significantly faster convergence of E vertical bar r(a, k)vertical bar towards 1 for any polynomial-time approximation algorithm. (c) 2006 Elsevier B.V. All rights reserved.
机译：在本文中，我们研究了蛋白质和基因网络的反向工程中出现的组合问题的计算复杂性。我们的贡献如下：我们提取问题的组合形式，并观察到，当“覆盖率”因子k是宇宙中元素数量的函数时，该问题与集合多重覆盖问题“等效”。对于我们的应用，一个重要的特殊情况是k = n-1。我们注意到，即使k是“大”，标准贪婪算法也会产生Omega（log n）的近似比率，即对于某些情况，k = n-c常数c>0。令1 0）E垂直线r（a，k）垂直线= 1的根a / k的线性函数朝着1减小。我们的随机算法是确定性和a的级联由数量β参数化的随机取整步骤，然后是剩余问题的贪婪解。我们还评论了对于任何多项式时间近似算法，E垂直线r（a，k）垂直线朝向1的收敛速度都不可能更快的可能性。 （c）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号