负载平衡及相关优化问题

【作者】 李伟东；

【导师】 李建平；

【作者基本信息】 云南大学 ， 应用数学， 2010， 博士

【摘要】 负载平衡问题是组合最优化领域中的热点问题之一,其目标函数通常有三类：最小化最大负载(简记为min-max)、最大化最小负载(简记为max-min)和最小化负载向量的lp-范数(简记为min-lp).本论文设计出了这三类目标函数下带各类约束的负载平衡问题的一些近似算法.本论文同时还研究了与负载平衡问题相关的推广的装箱问题和网络中的最小费用插点问题.全文分为十章：第一章介绍了研究的背景、基本定义和本论文的主要研究成果.第二章研究了等级约束下的负载平衡问题.当目标函数为min-max时,设计出了服务等级标号数为2的情形下的一个有效的多项式时间近似方案(简记为EPTAS),部分地解决了Ou等人[83]提出的问题,并设计出机器数为常数情形下的一个简单的运行时间为O(n)的全多项式时间近似方案(简记为FPTAS)；当目标函数为max-min时,设计出了一般情形下的多项式时间近似方案(简记为PTAS),服务等级标号数为常数情形下的一个EPTAS,机器数为常数情形下的一个运行时间为O(n)的FPTAS;当目标函数为min-lp时,设计出了一个对所有p都成立的2-近似算法,并设计出了机器数为固定常数的情形下的一个运行时间为O(n)的FPTAS.第三章研究了带数目约束的负载平衡问题.当目标函数为min-max时,证明了2-半匹配问题是3/2-ε不可近似的(这里ε>0),并设计出一个2-近似算法；当目标函数为max-min时,证明了2-半匹配问题是1/2+ε不可近似的(这里ε>0),并设计出一个1/2-近似算法；当目标函数为min-lp时,证明了2-半匹配问题是APX-难的,并设计出了一个2p-1/p-近似算法.第四章研究了划分拟阵约束下的负载平衡问题.当目标函数为min-max时,设计出了k为固定常数情形下的一个EPTAS和m为固定常数情形下的一个FPTAS;当目标函数为max-min时,设计出了一般情形下的一个击1/k-1-近似算法,k为固定常数情形下的一个EPTAS和m为固定常数情形下的一个FPTAS;当目标函数为min-lp时,设计出了一个全范数2-近似算法,从而推广了Wu和Yao[99]的结果,并设计出了m为固定常数情形下的一个FPTAS.第五章研究了拒绝费用受限的负载平衡问题.当目标函数为min-max时,设计出了一个PTAS,并设计出了机器数为固定常数的情形的一个运行时间为O(n2)的FPTAS,这改进了文献[4,105]中的结果；当目标函数为min-lp时,设计出了机器数为固定常数的情形下的一个FPTAS.第六章研究了带机器准备时间的负载平衡问题.当目标函数为min-max时,设计出了一个EPTAS,并设计出了机器数为固定常数的情形的一个运行时间为O(n)的FPTAS;设计出了一个通用目标函数下运行时间为O(n)的的EPTAS,推广了Alon等人[3]的结果.第七章研究了环上的负载平衡问题.证明了带拒绝费用的环上的负载平衡问题在流量可分的情形下依然是NP-难的,设计出了流量不可分的情形下了一个3-近似算法和流量可分的情形下的一个i/e-1-近似算法；利用一种新的取整技巧设计出了混合环上有向超图嵌入问题的一个2-近似算法；设计出了赋权环上有向超图嵌入问题的一个PTAS,从而推广了Li和Wang [76]的结果.第八章研究了两个推广的装箱问题.证明了拒绝费用受限的装箱问题是2-ε不可近似的,并设计出一个2-近似算法；设计出了凹费用装箱问题的一个运行时间为O(n)的渐近的多项式时间近似方案(简记为APTAS)和一个渐近的全多项式时间近似方案(简记为AFPTAS),从而解决了Leung和Li[71]提出的两个问题.第九章研究了网络中的插点问题.证明了(s,U)-插点问题是(1-ε)lnn-不可近似的,除非NP(?)TIME(nO(loglogn));证明了路上插点问题多项式等价于限制性的最短路问题,并设计出了一个新颖的动态规划算法来求得单位插点费用相同情形下的最优解；证明了树上插点问题多项式等价于限制性的最小支撑树问题,并设计出一个特殊情形下的最优算法.第十章对全文进行了总结并提出了二十个问题,为未来的研究指明了方向.更多还原

【Abstract】 Load balancing problem is one of the most active research topics in combina-torial optimization. Genenally, its objectives include three types:minimizing the maximum load (min-max, for short), maximizing the minimum load (max-min, for short) and minimizing the lp-norm of the load vector (min-lp, for short). We design some approximation algorithms for some load balancing problems with various con-straints under these three objectives. We also study some generalized bin packing problems which are closely related to the load balancing problem and some inserting vertices problems in the network.This dissertation is divided into ten chapters:Chapter 1 introduces the research background, basic concepts and our main results.In Chapter 2, we study the load balancing problem with hierarchical constraints. For the min-max objective, we present an efficient polynomial-time approximation scheme (EPTAS, for short) for the case where the number of grade of service levels is 2, which partially solves an open problem proposed by Ou et al. [83]. We also present a full polynomial-time approximation scheme (FPTAS, for short) with run-ning time O(n) for the case where the number of machines is fixed. For the max-min objective, we present a polynomial-time approximation scheme (PTAS, for short) for the general case, a EPTAS for the case where the number of grade of service levels is fixed, and a FPTAS with running time O(n) for the case where the number of machines is fixed, respectively. For the min-lp objective, we present an all-norm 2-approximation algorithm and a FPTAS with running time O(n) for the case where the number of machines is fixed.In Chapter 3, we study the load balancing problem with cardinality constraint. For the min-max objective, we prove that the 2-semimatching problem cannot be approximated within 3/2-(?), where (?)>0, and then present a 2-approximation algo-rithm; For the max-min objective, we prove that the 2-semimatching problem cannot be approximated better than 1/2, and then present a 1/2-approximation algorithm; ForThis research is supported by the National Natural Science Foundation of China (No. 10861012), Foundation of Younger Scholar in Science and Technology of Yunnan Province (No. 2007PY01-21) and Nature Science Foundation of Yunnan University (No.2009F04Z). the min-lp objective, we prove that the 2-semimatching problem is APX-hard, and then present a 2p-1/p-approximation algorithm.In Chapter 4, we study the load balancing problem with partition matroid constraint. For the min-max objective, we present a EPTAS for the case where k is fixed, and a FPTAS for the case where m is fixed. For the max-min objective, we present a 1/k-1-approximation algorithm for the general case, a EPTAS for the case where k is fixed, and a FPTAS for the case where m is fixed. For the min-lp objective, we present an all-norm 2-approximation algorithm which generalizes Wu and Yao’s result [100] and a FPTAS for the case where m is fixed.In Chapter 5, we study the rejection cost constrained load balancing problem. For the min-max objective, we present a PTAS for the general case and a FPTAS with running time O(n2) for the case where the number of machines is fixed, which improves the results in [4,105]. For the min-lp objective, we present a FPTAS for the case where the number of machines is fixed.In Chapter 6, we study the load balancing problem with machine release times. For the min-max objective, we present a EPTAS for the general case and a FPTAS with running time O(n) for the case where the number of machines is fixed. For the general objective, we present a EPTAS with running time O(n), which generalizes Alon et al.’s result [3].In Chapter 7, we study some ring load balancing problems. We prove that the ring loading problem with rejection cost is NP-hard even if the demand can be splitted. We present a 3-approximation algorithm for the case where the demand can not be splitted and a e/e-1-approximationn algorithm for the case where the demand can be splitted; We present a 2-approximation algorithm based on a novel rounding technique for the problem of embedding weighted directed hyperedges in a mixed cycle; We also present a PTAS for the problem of embedding a directed hyperedge in a weighted cycle, which generalizes Li and Wang’s result [76].In Chapter 8, we study two generalized bin packing problems. We prove that the rejection-cost-constrained bin packing problem can not be approximated within 2-(?), where (?)> 0, and then present a 2-approximation algorithm. We also present an asymptotic polynomial-time approximation scheme (APTAS, for short) and an asymptotic full polynomial-time approximation scheme (AFPTAS, for short) for the concave cost bin packing problem, which solves the problems proposed by Leung and Li [71].In Chapter 9, we study the inserting vertices problem in the network. We prove that (s, U)-inserting vertices problem cannot approximated within (1-(?))lnn, where (?)> 0, unless NP(?)TIME(nO(loglogn));We also prove that the inserting vertices problem on path is polynomially equivalent to the constrained shortest path problem, and then present an optimal algorithm for the case where the unit inserting costs are equal; We prove that the inserting vertices problem on tree is polynomially equivalent to the constrained minimum spanning tree problem, and then present an optimal algorithm for a special case.In Chapter 10, we provide some conclusions of the dissertation and propose twenty problems which would be important topics in future.更多还原