若干组合优化问题的近似算法设计与分析

摘要

该文主要研究组合优化中若干问题的近似算法.文章首先介绍了组合优化的概貌,给出了近似算法定义及其性能度量标准.在第二章至第五章中,我们分别研究了四个组合优化问题的近似算法,并给出了它们的性能分析.第二章研究了以极大化最小负载为目标的3-分划问题和带核3-分划问题.我们证明了对3-分划问题,MLPT算法的最坏情况界为(3m-1)/(4m-2)对带核3-分划问题,MLPT算法的最坏情况界(2m-1)/(3m-2),且上述界都是紧的.第三章研究带核3-分划问题的对偶算法.我们分别讨论了目标函数为极小化最大负载和极大化最小负载两种情形,给出了最坏情况界分别为5/4〔1+(1/2)<'k>〕和3/4〔1-(1/2)<'k>〕的近似算法.从最坏情况界角度来看,它们优于MLPT算法.第四章研究工件实时到达在线平行机排序问题Pm|r<,i>,online|C<,max>.我们证明当m>2时,问题的下界为(3-√5)/2,并给出了两台机情形的近似算法RL,它的竞争比为(18-√5)/11,上述结果均改进了文献中的已有结果.第五章研究了离线平行机排序问题的线性时间近似算法.我们证明了对三台机情形,算法D的最坏情况界为15/13,该算法的最坏情况界和时间复杂性优于除近似方案以外的已有近似算法.

目录

文摘

英文文摘

致谢

第一章绪论

§1.1组合优化简介

§1.2算法和计算复杂性

§1.3论文概述

第二章极大化最小负载目标3-分划问题

§2.1分划问题简介

§2.2 3-分划问题

§2.3带核3-分划问题

第三章带核3-分划问题的对偶算法

§3.1对偶算法简介

§3.2极小化最大负载目标下的带核3-分划问题

§3.3极大化最小负载目标下的带核3-分划问题

§4.1实时在线问题简介

§4.2 m＞2时下界的改进

§4.3m=2时改进算法RL

第五章三台平行机排序问题快速高效算法研究

§5.1引言及算法

§5.2 t=11，10，9时的证明

§5.3 t=8，7时的证明

§5.3 t≤6时的证明

附录

参考文献

攻读学位期间完成的论文与著作