...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Domination analysis for minimum multiprocessor scheduling
【24h】

Domination analysis for minimum multiprocessor scheduling

机译：最小多处理器调度的控制分析

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

摘要

Let P be a combinatorial optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A, s) is the maximal real q such that the solution x(I) obtained by A for any instance I of P of size s is not worse than at least the fraction q of the feasible solutions of I. We say that P admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm A for P such that lim(s ->infinity) domr(A, s) = 1. Alon, Gutin and Krivelevich [Algorithms with large domination ratio, J. Algorithms 50 (2004) 118-131] proved that the partition problem admits an ADRO algorithm. We extend their result to the minimum multiprocessor scheduling problem. (c) 2006 Elsevier B.V. All rights reserved.
机译：令P为组合优化问题，令A为P的近似算法。支配比domr（A，s）为最大实数q，使得A对P的任意实例I求出的解x（I）大小s至少不小于I的可行解的分数q。我们说，如果对于P有多项式时间近似算法A使得lim（s->无穷）domr（A，s）=1。Alon，Gutin和Krivelevich [具有较大支配率的算法，J。算法50（2004）118-131]证明分区问题允许使用ADRO算法。我们将其结果扩展到最小的多处理器调度问题。 （c）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号