学位论文 > 优秀研究生学位论文题录展示

覆盖约束条件下的平行机排序问题的算法研究

作　者: 崔振华
导　师: 王振波
学　校: 清华大学
专　业: 数学
关键词: 近似比顶点覆盖平行机排序 Local Ratio LPT
分类号: O223
类　型: 硕士论文
年　份: 2013年
下　载: 4次
引　用: 0次
阅　读: 论文下载

内容摘要

平行机排序问题随着其约束条件及目标函数的不同而有许多种变形。本文研究了以覆盖问题作为约束条件的平行机排序问题，是一种以两个组合优化问题作为基本模型的组合问题。本文通过探讨各个组合优化问题的性质，并结合组合问题所具有独特的结构，提出了有效的近似算法。本文以顶点覆盖及一般的覆盖问题作为约束条件，结合了平行机排序问题的经典算法LPT算法以及覆盖问题的近似算法Local Ratio,给出了一系列的近似算法。其中对于顶点覆盖约束下的平行机排序问题，给出了(3-2/(m+1))近似比的LLR算法，其中m为机器数目。此外对于m=2的情形我们给出了2近似比的LRBi算法；随后我们将LLR算法的想法推广到对于一般覆盖约束条件下的平行机排序问题模型，给出了(r+max{0,(m-r)/r})近似比的LArE算法，其中r表示覆盖问题的Ar算法的近似比；最后我们给出可任意近似到(r+∈)近似比的LArE_∈算法，并与之前的结果进行了比较。本文的创新点如下：1、关于平行机排序和顶点覆盖的组合问题给出(3-2/(m+1))近似算法。2、在组合算法的基础上，融入了在一定条件下进行枚举的思想，从而得到更有效的算法。3、关于平行机排序和覆盖问题的组合问题，当机器数目固定时本文给出近似比最优的多项式时间算法。

全文目录

摘要  3-4
Abstract  4-6
第1章引言  6-9
  1.1 研究背景  6-7
  1.2 主要贡献  7-8
  1.3 本文介绍  8-9
第2章预备理论  9-13
  2.1 P_m||C_(max)及LPT算法  9-10
  2.2 顶点覆盖问题及Local Ratio算法  10-11
  2.3 覆盖约束下的平行机排序问题  11-13
第3章顶点覆盖约束下的平行机排序问题  13-20
  3.1 LLR算法  13-17
  3.2 对于2台机器的情形  17-20
第4章一般覆盖约束下的平行机排序问题  20-29
  4.1 LArE_∈算法  20-22
  4.2 LArE_∈算法  22-26
    4.2.1 r>1的情形  24-26
    4.2.2 r = 1的情形  26
  4.3 应用实例  26-29
    4.3.1 P_m|VC|_(Cmax)中的应用  26-28
    4.3.2 给定m的情形  28-29
第5章结束语  29-31
参考文献  31-33
致谢  33-35
个人简历、在学期间发表的学术论文与研究成果  35

覆盖约束条件下的平行机排序问题的算法研究

内容摘要

全文目录

相似论文