负载平衡及相关优化问题
|
摘要
负载平衡问题是组合最优化领域中的热点问题之一,其目标函数通常有三类：最小化最大负载(简记为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));证明了路上插点问题多项式等价于限制性的最短路问题,并设计出了一个新颖的动态规划算法来求得单位插点费用相同情形下的最优解；证明了树上插点问题多项式等价于限制性的最小支撑树问题,并设计出一个特殊情形下的最优算法.
第十章对全文进行了总结并提出了二十个问题,为未来的研究指明了方向.
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; For
This 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.
全文分为十章：
第一章介绍了研究的背景、基本定义和本论文的主要研究成果.
第二章研究了等级约束下的负载平衡问题.当目标函数为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));证明了路上插点问题多项式等价于限制性的最短路问题,并设计出了一个新颖的动态规划算法来求得单位插点费用相同情形下的最优解；证明了树上插点问题多项式等价于限制性的最小支撑树问题,并设计出一个特殊情形下的最优算法.
第十章对全文进行了总结并提出了二十个问题,为未来的研究指明了方向.
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; For
This 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.
引文
[1]R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows:Theory, Algorithms, and Applications, Prentice Hall, NJ,1993.
[2]N. Alon, Y. Azar, G. J.Woeginger, and T. Yadid, Approximation schemes for schedul-ing, in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),1997,493-500.
[3]N. Alon, Y. Azar, G. J.Woeginger, and T. Yadid, Approximation schemes for schedul-ing on parallel machines, Journal of Scheduling 1 (1998) 55-66.
[4]E. Angel, E. Bampis, and A. Kononov, A FPTAS for approximating the unrelated parallel machines scheduling problem with costs, Lecture Notes in Computer Science 2161, ESA 2001,194-205.
[5]S. Anily, J. Bramel, and D. Simchi-Levi, Worst-case analysis of heuristics for the bin packing problem with general cost structures, Operations Research 42 (1994) 287-298.
[6]A. Asadpour and A. Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC),2007,114-121.
[7]Y. Azar and A. Epstein, Convex programming for scheduling unrelated parallel ma-chines, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC),2005,331-337.
[8]Y. Azar, L. Epstein, Y. Richter, and G.J. Woeginger, All-norm approximation algo-rithms, Journal of Algorithms 52 (2004) 120-133.
[9]Y. Azar and S. Taub, All-Norm approximation for scheduling on identical machines, Lecture Notes in Computer Science 3111, SWAT 2004,298-310.
[10]L.Babel, H. Kellerer, and V. Kotov, The k-partitioning problem, Mathematical Meth-ods of Operations Research 47 (1998) 59-82.
[11]N. Bansal and M. Sviridenko, The Santa Claus Problem, in Proceedings of the 38th Annual ACM Symposium on the Theory of Computation (STOC),2006,31-40.
[12]M. Bateni, M. Charikar, and V. Guruswami, Maxmin allocation via degree lower-bounded arborescences, In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC),2009,543-552.
[13]W. Bein, J.R. Correa, and X. Han, A fast asymptotic approximation scheme for bin packing with rejection, Theoretical Computer Science 393 (2008) 14-22.
[14]R. Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1958), 87-90.
[15]M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest, and R.E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences 7(1973) 448-461.
[16]J.A. Bondy and U.S. R. Murty, Graph Theory with Application, London:Macmillan Press,1976.
[17]P. Brucker, Scheduling Algorithms, Springer, Berlin,2004.
[18]M.Bruglieri, M. Ehrgott, H.W. Hamacher, and F. Maffioli, An annotated bibliogra-phy of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics 154 (2006) 1344-1357.
[19]D. Chakrabarty, J. Chuzhoy, and S. Khanna, On allocating goods to maximize fair-ness, in Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),2009,107-116.
[20]S.Y. Chang and H.-C. Hwang, The worst case analysis of the Multifit algorithm for scheduling nonsimultaneous parallel machines, Discrete Applied Mathematics 92 (1999) 135-147.
[21]M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Ap-proximation algorithms for directed steiner problems, Journal of Algorithms 33 (1999) 73-91.
[22]D. Chen, D.Z. Du, X.D. Hu, G. Lin, L. Wang, and G. Xue, Approximations for steiner trees with minimum number of steiner points, Journal of Global Optimization 18 (2000) 17-33.
[23]S.P. Chen, Y. He, and G.H. Lin,3-partitioning for maximizing the minimum load, Journal of Combinatorial Optimization 6 (2002) 67-80.
[24]M. Dell'Amico, M. Iori, and S. Martello, Heuristic algorithms and scatter search for the cardinality constrained P││Cmax problem, Journal of Heuristics 10 (2004) 169-204.
[25]M. Dell'Amico, M. Iori, S. Martello, and M. Monaci, Lower bound and heuristic algorithms for the ki; partitioning problem, European Journal of Operational Research 171 (2006) 725-742.
[26]M. Dell'Amico and S. Martello, Bounds for the cardinality constrained P││Cmax prob-lem, Journal of Scheduling 4 (2001) 123-138.
[27]P. Dell'Olmo, P. Hansen, S. Pallottino, and G. Storchi, On uniform k-partition problems, Discrete Applied Mathematics 150 (2005) 121-139.
[28]G. Dosa and Y. He, Bin packing problems with rejection penalties and their dual problems, Information and Computation 204 (2006) 795-815. Preliminary version in Proceedings of COCOON 2005,885-894.
[29]R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer,1999.
[30]T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing:A special case of scheduling unrelated parallel machines, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),2008,483-490.
[31]L. Epstein, Bin packing with rejection revisited, Algorithmica 56 (2010) 505-528. Preliminary version in Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA),2007,146-159.
[32]L. Epstein and A. Levin, AFPTAS results for common variants of bin packing:A new method to handle the small items, manuscript,2007.
[33]L. Epstein and A. Levin, Bin packing with general cost structures, manuscript,2009.
[34]F. Ergun, R. Sinha, and L. Zhang, An improved FPTAS for restricted shortest path, Information Processing Letters 83 (2002) 287-291.
[35]范静,杨启帆,带机器准备时间的三台平行机排序问题的线性时间算法,浙江大学学报(理学版),32(2005)258-263.
[36]U. Feige, A threshold of lnn for approximating set cover, Journal of the Association for Computing Machinery 45 (1998) 634-652.
[37]U. Feige, On allocations that maximize fairness, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),2008,287-293.
[38]W. Fernandez de la Vega and G.S. Lueker, Bin packing can be solved within 1+(?) in linear time, Combinatorica 1 (1981) 349-355.
[39]A. Fishkin, K. Jansen, and M. Mastrolilli, Grouping techniques for scheduling prob-lems:simpler and faster, in Proceedings of the 9th Annual European Symposium on Algorithms (ESA),2001,206-217.
[40]J. L. Ganley and J. P. Cohoon, Minimum-congestion hypergraph embedding in a cycle, IEEE Transactions on Computers 46 (1997) 600-602.
[41]M.R. Garey and D. S. Johnson, Computer and Intractability:A Guide to The Theory of NP-Completeness, San Francisco:W. H. Freeman and Company,1979.
[42]T. Gonzalez, Improved approximation algorithm for embedding hypergraphs in a cycle, Information Processing Letters 67 (1998) 267-271.
[43]R.L. Graham, Bounds on multiprocessor timing anomalies, SIAM Journal on Applied Mathematics 17(1969) 416-429.
[44]R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling:a survey, Annals of Discrete Mathematics 5 (1979) 287-326.
[45]Q.P. Gu and Y. Wang, Efficient algorithms for minimum congestion hypergraph em-bedding in a cycle, IEEE Transactions on Parallel & Distributed Systems 17 (2006) 205-214.
[46]R. Hassin, Approximation schemes for the restricted shortest path problem, Mathe-matics of Operations Research 17(1992) 36-42.
[47]R. Hassin and A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem, SIAM Journal on Computing 33 (2004) 261-268.
[48]Y. He, The Multifit algorithm for set partitioning containing kernel, Applied Mathe-matics:A Journal of Chinese Universities 14 (1999) 227-232.
[49]Y. He, Z.Y. Tan, J. Zhu, and E. Yao,k-Partitioning problems for maximizing the minimum load, Computers and Mathematics with Applications 46 (2003) 1671-1681.
[50]H. Ho and S. Lee, Improved approximation algorithms for weighted hypergraph em-bedding in a cycle, SIAM Journal on Optimization 18 (2008) 1490-1500.
[51]D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, MA,1995.
[52]D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedul-ing problems:theoretical and practical results, Journal of the Association for Comput-ing Machinery 34 (1987) 144-162.
[53]H. Hoogeveen, M. Skutella, and G.J. Woeginger, Preemptive scheduling with rejec-tion, Mathematical Programming 94 (2003) 361-374.
[54]E. Horowitz and S. Sahni, Exact and approximate algorithms for scheduling non-identical processors, Journal of the Association for Computing Machinery 23 (1976) 317-327.
[55]Y. Huo and J.Y.-T. Leung, Parallel machine scheduling with nested processing set restrictions, European Journal of Operational Research 204 (2010) 229-236.
[56]H.C. Hwang, S.Y. Chang, and K. Lee, Parallel machine scheduling under a grade of service provision, Computers & Operations Research 31 (2004) 2055-2061.
[57]H.C. Hwang, K. Lee, and S.Y. Chang, The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics,148 (2005),49-61.
[58]K. Jansen and L. Porkolab, Improved Approximation Schemes for Scheduling Unre-lated Parallel Machines, in Proceedings of the 31th Annual ACM Symposium on Theory of Computing (STOC),1999,408-417.
[59]M. Ji and T.C.E. Cheng, An FPTAS for parallel machine scheduling under a grade of service provision to minimize makespan, Information Processing Letters 108 (2008) 171-174.
[60]季敏,何勇,带核集分划问题的一个改进近似算法,系统工程理论与实践12(2003)110-115.
[61]Y. Jiang. On line scheduling on parallel machines with two GoS levels. Journal of Combinatorial Optimization 16 (2008) 28-38.
[62]N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, in Proceedings of the 23rd Annual Symposiumon Foundation of Computer Science (FOCS),1982,312-320.
[63]H. Kellerer, Algorithms for multiprocessor scheduling with machine release times, HE Transactions 30 (1998) 991-999.
[64]H. Kellerer and V. Kotov, A7/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling, INFOR 37 (1999) 48-56.
[65]H. Kellerer and G. Woeginger, A tight bound for 3-partitioning, Discrete Applied Mathematics 45 (1993) 249-259.
[66]C.Y. Lee, Parallel machine scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics 30 (1991) 53-61.
[67]C.Y. Lee, Y. He, and G. Tang, A note on "parallel machine scheduling with nonsimul-taneous machine available time", Discrete Applied Mathematics 100 (2000) 133-135.
[68]S.L. Lee and H.-J. Ho, On minimizing the maximum congestion for weighted hyper-graph embedding in a cycle, Information Processing Letters 87 (2003) 271-275.
[69]H.W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research 8 (1983) 538-548.
[70]J.K. Lenstra, D.B. Shmoys, and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming 46 (1990) 259-271.
[71]J.Y.-T. Leung and C.-L.Li, An asymptotic approximation scheme for the concave cost bin packing problem, European Journal of Operational Research 191 (2008) 582-586.
[72]J.Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions:A survey, International Journal of Production Economics 116 (2008) 251-262.
[73]C.-L. Li and Z.-L. Chen, Bin-packing problem with concave costs of bin utilization, Naval Research Logistics 53 (2006) 298-308.
[74]C.-S. Li, F.F. Tong, C.J. Georgiou, and M. Chen, Gain equalization in metropolitan and wide area optical networks using optical amplifiers, in Proceedings of INFOCOM'94, 1994,130-137.
[75]G. Li, X. Deng, and Y. Xu, A polynomial-time approximation scheme for embedding hypergraph in a cycle, ACM Transactions on Algorithms,5 (2009), Article No.20.
[76]K. Li and L. Wang, A polynomial time approximation scheme for embedding a di-rected hypergraph on a ring, Information Processing Letters 97 (2006) 203-207.
[77]M. Li, B. Ma, and L. Wang, On the closest string and substring problems, Journal of the Association for Computing Machinery 49 (2002) 157-171.
[78]D. Marx, Parametrized complexity and approximation algorithms, The Computer Journal,51 (2008) 60-78.
[79]R. Motwani and P. Raghavan, Randomized Algorithm, Cambridge University Press, 1995.
[80]G. Muratore, U.M. Schwarz, and G.J. Woeginger, Parallel machine scheduling with nested job assignment restrictions, Operations Research Letters 38 (2010) 47-50.
[81]F.D. Murgolo, An efficient approximation scheme for variable-sized bin packing, SIAM Journal on Computing 16 (1987) 149-161.
[82]Y.S. Myung, An Efficient algorithm for the ring loading problem with integer demand splitting, SIAM Journal on Discrete Mathematics 14 (2001) 291-298.
[83]J. Ou, J.Y.-T. Leung, and C.L. Li, Scheduling parallel machines with inclusive pro-cessing set restrictions, Naval Research Logistics 55 (2008) 328-338.
[84]C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:Algorithms and Complexity, Prentice-Hall,1982;刘振宏,蔡茂诚译,组合优化：算法和复杂性[M],北京：清华大学出版社,1987.
[85]C. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences 43 (1991) 425-440.
[86]E. Petrank, The hardness of approximation:gap location, Computational Complexity 4 (1994) 133-157.
[87]B. Ramamurthy, J. Iness, and B. Mukherjee, Minimizing the number of optical am-plifiers needed to support a multi-wavelength optical LAN/MAN, in Proceedings of the INFOCOM'97,1997,261-268.
[88]R. Ravi and M. X. Goemans, The constrained minimum spanning tree problem (ex-tended abstract), in Proceedings of the 5th Scandinavian Workshop on Algorithm The-ory,1996,66-75.
[89]A. Schrijver, P. Seymour, and P. Winkler, The ring loading problem, SIAM Review 41 (1999) 777-791.
[90]D.B. Shmoys and E. Tardos, An approximation algorithm for the generalized as-signment problem, Mathematical Programming 62 (1993) 461-74. Preliminary version appeared in Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algo-rithms (SODA),1993,448-454.
[91]谈之奕,何勇,带机器准备时间的平行机在线与半在线排序,系统科学与数学22(2000)414-421.
[92]Z. Tan and A. Zhang, A mathematical programming approach for online hierarchical scheduling, in Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA),2009,438-450.
[93]V.V. Vazirani, Approximation Algorithms, Springer,2001.
[94]B.F. Wang, Linear time algorithms for the ring loading problem with demand split-ting, Journal of Algorithms 54 (2005) 45-57.
[95]I. Wegener, Complexity Theory:Exploring the Limit of Efficient Algorithms, Springer,2004.
[96]G. J. Woeginger, When does a dynamic programming formulation guarantee the exis-tence of a fully polynomial time approximation scheme (FPTAS)?, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),1999,820-829.
[97]G.J. Woeginger, A polynomial-time approximation scheme for maximizing the mini-mum machine completion time, Operations Research Letters 20 (1997) 149-154.
[98]吴彪,拟阵约束下的分划问题研究,浙江大学博士毕业论文,2007.
[99]B. Wu and E. Yao, k-Partitioning problems with partition matroid constraint, The-oretical Computer Science 374 (2007) 41-48.
[100]B. Wu and E. Yao, Lower bounds and modified LPT algorithm for k-partitioning problems with partition matroid constraint, Applied Mathematics:A Journal of Chinese Universities 23 (2008) 1-8.
[101]杨朝霞,超图嵌入带权重圈的一个2-近似算法,山东大学学报43(2008)11-13.
[102]A. Zelikovsky, A series of approximation algorithms for the acyclic directed steiner tree problem, Algorithmica 18 (1997) 99-110.
[103]A. Zhang, Y. Jiang, and Z. Tan, Online parallel machines scheduling with two hier-archies, Theoretical Computer Science 410 (2009) 3597-3605.
[104]C. Zhang, G. Wang, X. Liu, and J. Liu, Approximating scheduling machines with capacity constraints, in Proceedings of the 3rd International Workshop on Frontiers in Algorithmics,2009,283-292.
[105]Y. Zhang, J. Ren, and C. Wang, Scheduling with rejection to minimize the makespan. In Proceedings of the 3rd Annual International Conference on Combinatorial Optimiza-tion and Applications (COCOA),2009,411-420.
[106]周萍,蒋义伟,何勇,有两个服务等级的平行机排序问题,高校应用数学学报22(2007)275-284.
[2]N. Alon, Y. Azar, G. J.Woeginger, and T. Yadid, Approximation schemes for schedul-ing, in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),1997,493-500.
[3]N. Alon, Y. Azar, G. J.Woeginger, and T. Yadid, Approximation schemes for schedul-ing on parallel machines, Journal of Scheduling 1 (1998) 55-66.
[4]E. Angel, E. Bampis, and A. Kononov, A FPTAS for approximating the unrelated parallel machines scheduling problem with costs, Lecture Notes in Computer Science 2161, ESA 2001,194-205.
[5]S. Anily, J. Bramel, and D. Simchi-Levi, Worst-case analysis of heuristics for the bin packing problem with general cost structures, Operations Research 42 (1994) 287-298.
[6]A. Asadpour and A. Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC),2007,114-121.
[7]Y. Azar and A. Epstein, Convex programming for scheduling unrelated parallel ma-chines, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC),2005,331-337.
[8]Y. Azar, L. Epstein, Y. Richter, and G.J. Woeginger, All-norm approximation algo-rithms, Journal of Algorithms 52 (2004) 120-133.
[9]Y. Azar and S. Taub, All-Norm approximation for scheduling on identical machines, Lecture Notes in Computer Science 3111, SWAT 2004,298-310.
[10]L.Babel, H. Kellerer, and V. Kotov, The k-partitioning problem, Mathematical Meth-ods of Operations Research 47 (1998) 59-82.
[11]N. Bansal and M. Sviridenko, The Santa Claus Problem, in Proceedings of the 38th Annual ACM Symposium on the Theory of Computation (STOC),2006,31-40.
[12]M. Bateni, M. Charikar, and V. Guruswami, Maxmin allocation via degree lower-bounded arborescences, In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC),2009,543-552.
[13]W. Bein, J.R. Correa, and X. Han, A fast asymptotic approximation scheme for bin packing with rejection, Theoretical Computer Science 393 (2008) 14-22.
[14]R. Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1958), 87-90.
[15]M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest, and R.E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences 7(1973) 448-461.
[16]J.A. Bondy and U.S. R. Murty, Graph Theory with Application, London:Macmillan Press,1976.
[17]P. Brucker, Scheduling Algorithms, Springer, Berlin,2004.
[18]M.Bruglieri, M. Ehrgott, H.W. Hamacher, and F. Maffioli, An annotated bibliogra-phy of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics 154 (2006) 1344-1357.
[19]D. Chakrabarty, J. Chuzhoy, and S. Khanna, On allocating goods to maximize fair-ness, in Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),2009,107-116.
[20]S.Y. Chang and H.-C. Hwang, The worst case analysis of the Multifit algorithm for scheduling nonsimultaneous parallel machines, Discrete Applied Mathematics 92 (1999) 135-147.
[21]M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Ap-proximation algorithms for directed steiner problems, Journal of Algorithms 33 (1999) 73-91.
[22]D. Chen, D.Z. Du, X.D. Hu, G. Lin, L. Wang, and G. Xue, Approximations for steiner trees with minimum number of steiner points, Journal of Global Optimization 18 (2000) 17-33.
[23]S.P. Chen, Y. He, and G.H. Lin,3-partitioning for maximizing the minimum load, Journal of Combinatorial Optimization 6 (2002) 67-80.
[24]M. Dell'Amico, M. Iori, and S. Martello, Heuristic algorithms and scatter search for the cardinality constrained P││Cmax problem, Journal of Heuristics 10 (2004) 169-204.
[25]M. Dell'Amico, M. Iori, S. Martello, and M. Monaci, Lower bound and heuristic algorithms for the ki; partitioning problem, European Journal of Operational Research 171 (2006) 725-742.
[26]M. Dell'Amico and S. Martello, Bounds for the cardinality constrained P││Cmax prob-lem, Journal of Scheduling 4 (2001) 123-138.
[27]P. Dell'Olmo, P. Hansen, S. Pallottino, and G. Storchi, On uniform k-partition problems, Discrete Applied Mathematics 150 (2005) 121-139.
[28]G. Dosa and Y. He, Bin packing problems with rejection penalties and their dual problems, Information and Computation 204 (2006) 795-815. Preliminary version in Proceedings of COCOON 2005,885-894.
[29]R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer,1999.
[30]T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing:A special case of scheduling unrelated parallel machines, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),2008,483-490.
[31]L. Epstein, Bin packing with rejection revisited, Algorithmica 56 (2010) 505-528. Preliminary version in Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA),2007,146-159.
[32]L. Epstein and A. Levin, AFPTAS results for common variants of bin packing:A new method to handle the small items, manuscript,2007.
[33]L. Epstein and A. Levin, Bin packing with general cost structures, manuscript,2009.
[34]F. Ergun, R. Sinha, and L. Zhang, An improved FPTAS for restricted shortest path, Information Processing Letters 83 (2002) 287-291.
[35]范静,杨启帆,带机器准备时间的三台平行机排序问题的线性时间算法,浙江大学学报(理学版),32(2005)258-263.
[36]U. Feige, A threshold of lnn for approximating set cover, Journal of the Association for Computing Machinery 45 (1998) 634-652.
[37]U. Feige, On allocations that maximize fairness, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),2008,287-293.
[38]W. Fernandez de la Vega and G.S. Lueker, Bin packing can be solved within 1+(?) in linear time, Combinatorica 1 (1981) 349-355.
[39]A. Fishkin, K. Jansen, and M. Mastrolilli, Grouping techniques for scheduling prob-lems:simpler and faster, in Proceedings of the 9th Annual European Symposium on Algorithms (ESA),2001,206-217.
[40]J. L. Ganley and J. P. Cohoon, Minimum-congestion hypergraph embedding in a cycle, IEEE Transactions on Computers 46 (1997) 600-602.
[41]M.R. Garey and D. S. Johnson, Computer and Intractability:A Guide to The Theory of NP-Completeness, San Francisco:W. H. Freeman and Company,1979.
[42]T. Gonzalez, Improved approximation algorithm for embedding hypergraphs in a cycle, Information Processing Letters 67 (1998) 267-271.
[43]R.L. Graham, Bounds on multiprocessor timing anomalies, SIAM Journal on Applied Mathematics 17(1969) 416-429.
[44]R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling:a survey, Annals of Discrete Mathematics 5 (1979) 287-326.
[45]Q.P. Gu and Y. Wang, Efficient algorithms for minimum congestion hypergraph em-bedding in a cycle, IEEE Transactions on Parallel & Distributed Systems 17 (2006) 205-214.
[46]R. Hassin, Approximation schemes for the restricted shortest path problem, Mathe-matics of Operations Research 17(1992) 36-42.
[47]R. Hassin and A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem, SIAM Journal on Computing 33 (2004) 261-268.
[48]Y. He, The Multifit algorithm for set partitioning containing kernel, Applied Mathe-matics:A Journal of Chinese Universities 14 (1999) 227-232.
[49]Y. He, Z.Y. Tan, J. Zhu, and E. Yao,k-Partitioning problems for maximizing the minimum load, Computers and Mathematics with Applications 46 (2003) 1671-1681.
[50]H. Ho and S. Lee, Improved approximation algorithms for weighted hypergraph em-bedding in a cycle, SIAM Journal on Optimization 18 (2008) 1490-1500.
[51]D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, MA,1995.
[52]D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedul-ing problems:theoretical and practical results, Journal of the Association for Comput-ing Machinery 34 (1987) 144-162.
[53]H. Hoogeveen, M. Skutella, and G.J. Woeginger, Preemptive scheduling with rejec-tion, Mathematical Programming 94 (2003) 361-374.
[54]E. Horowitz and S. Sahni, Exact and approximate algorithms for scheduling non-identical processors, Journal of the Association for Computing Machinery 23 (1976) 317-327.
[55]Y. Huo and J.Y.-T. Leung, Parallel machine scheduling with nested processing set restrictions, European Journal of Operational Research 204 (2010) 229-236.
[56]H.C. Hwang, S.Y. Chang, and K. Lee, Parallel machine scheduling under a grade of service provision, Computers & Operations Research 31 (2004) 2055-2061.
[57]H.C. Hwang, K. Lee, and S.Y. Chang, The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics,148 (2005),49-61.
[58]K. Jansen and L. Porkolab, Improved Approximation Schemes for Scheduling Unre-lated Parallel Machines, in Proceedings of the 31th Annual ACM Symposium on Theory of Computing (STOC),1999,408-417.
[59]M. Ji and T.C.E. Cheng, An FPTAS for parallel machine scheduling under a grade of service provision to minimize makespan, Information Processing Letters 108 (2008) 171-174.
[60]季敏,何勇,带核集分划问题的一个改进近似算法,系统工程理论与实践12(2003)110-115.
[61]Y. Jiang. On line scheduling on parallel machines with two GoS levels. Journal of Combinatorial Optimization 16 (2008) 28-38.
[62]N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, in Proceedings of the 23rd Annual Symposiumon Foundation of Computer Science (FOCS),1982,312-320.
[63]H. Kellerer, Algorithms for multiprocessor scheduling with machine release times, HE Transactions 30 (1998) 991-999.
[64]H. Kellerer and V. Kotov, A7/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling, INFOR 37 (1999) 48-56.
[65]H. Kellerer and G. Woeginger, A tight bound for 3-partitioning, Discrete Applied Mathematics 45 (1993) 249-259.
[66]C.Y. Lee, Parallel machine scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics 30 (1991) 53-61.
[67]C.Y. Lee, Y. He, and G. Tang, A note on "parallel machine scheduling with nonsimul-taneous machine available time", Discrete Applied Mathematics 100 (2000) 133-135.
[68]S.L. Lee and H.-J. Ho, On minimizing the maximum congestion for weighted hyper-graph embedding in a cycle, Information Processing Letters 87 (2003) 271-275.
[69]H.W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research 8 (1983) 538-548.
[70]J.K. Lenstra, D.B. Shmoys, and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming 46 (1990) 259-271.
[71]J.Y.-T. Leung and C.-L.Li, An asymptotic approximation scheme for the concave cost bin packing problem, European Journal of Operational Research 191 (2008) 582-586.
[72]J.Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions:A survey, International Journal of Production Economics 116 (2008) 251-262.
[73]C.-L. Li and Z.-L. Chen, Bin-packing problem with concave costs of bin utilization, Naval Research Logistics 53 (2006) 298-308.
[74]C.-S. Li, F.F. Tong, C.J. Georgiou, and M. Chen, Gain equalization in metropolitan and wide area optical networks using optical amplifiers, in Proceedings of INFOCOM'94, 1994,130-137.
[75]G. Li, X. Deng, and Y. Xu, A polynomial-time approximation scheme for embedding hypergraph in a cycle, ACM Transactions on Algorithms,5 (2009), Article No.20.
[76]K. Li and L. Wang, A polynomial time approximation scheme for embedding a di-rected hypergraph on a ring, Information Processing Letters 97 (2006) 203-207.
[77]M. Li, B. Ma, and L. Wang, On the closest string and substring problems, Journal of the Association for Computing Machinery 49 (2002) 157-171.
[78]D. Marx, Parametrized complexity and approximation algorithms, The Computer Journal,51 (2008) 60-78.
[79]R. Motwani and P. Raghavan, Randomized Algorithm, Cambridge University Press, 1995.
[80]G. Muratore, U.M. Schwarz, and G.J. Woeginger, Parallel machine scheduling with nested job assignment restrictions, Operations Research Letters 38 (2010) 47-50.
[81]F.D. Murgolo, An efficient approximation scheme for variable-sized bin packing, SIAM Journal on Computing 16 (1987) 149-161.
[82]Y.S. Myung, An Efficient algorithm for the ring loading problem with integer demand splitting, SIAM Journal on Discrete Mathematics 14 (2001) 291-298.
[83]J. Ou, J.Y.-T. Leung, and C.L. Li, Scheduling parallel machines with inclusive pro-cessing set restrictions, Naval Research Logistics 55 (2008) 328-338.
[84]C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:Algorithms and Complexity, Prentice-Hall,1982;刘振宏,蔡茂诚译,组合优化：算法和复杂性[M],北京：清华大学出版社,1987.
[85]C. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences 43 (1991) 425-440.
[86]E. Petrank, The hardness of approximation:gap location, Computational Complexity 4 (1994) 133-157.
[87]B. Ramamurthy, J. Iness, and B. Mukherjee, Minimizing the number of optical am-plifiers needed to support a multi-wavelength optical LAN/MAN, in Proceedings of the INFOCOM'97,1997,261-268.
[88]R. Ravi and M. X. Goemans, The constrained minimum spanning tree problem (ex-tended abstract), in Proceedings of the 5th Scandinavian Workshop on Algorithm The-ory,1996,66-75.
[89]A. Schrijver, P. Seymour, and P. Winkler, The ring loading problem, SIAM Review 41 (1999) 777-791.
[90]D.B. Shmoys and E. Tardos, An approximation algorithm for the generalized as-signment problem, Mathematical Programming 62 (1993) 461-74. Preliminary version appeared in Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algo-rithms (SODA),1993,448-454.
[91]谈之奕,何勇,带机器准备时间的平行机在线与半在线排序,系统科学与数学22(2000)414-421.
[92]Z. Tan and A. Zhang, A mathematical programming approach for online hierarchical scheduling, in Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA),2009,438-450.
[93]V.V. Vazirani, Approximation Algorithms, Springer,2001.
[94]B.F. Wang, Linear time algorithms for the ring loading problem with demand split-ting, Journal of Algorithms 54 (2005) 45-57.
[95]I. Wegener, Complexity Theory:Exploring the Limit of Efficient Algorithms, Springer,2004.
[96]G. J. Woeginger, When does a dynamic programming formulation guarantee the exis-tence of a fully polynomial time approximation scheme (FPTAS)?, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),1999,820-829.
[97]G.J. Woeginger, A polynomial-time approximation scheme for maximizing the mini-mum machine completion time, Operations Research Letters 20 (1997) 149-154.
[98]吴彪,拟阵约束下的分划问题研究,浙江大学博士毕业论文,2007.
[99]B. Wu and E. Yao, k-Partitioning problems with partition matroid constraint, The-oretical Computer Science 374 (2007) 41-48.
[100]B. Wu and E. Yao, Lower bounds and modified LPT algorithm for k-partitioning problems with partition matroid constraint, Applied Mathematics:A Journal of Chinese Universities 23 (2008) 1-8.
[101]杨朝霞,超图嵌入带权重圈的一个2-近似算法,山东大学学报43(2008)11-13.
[102]A. Zelikovsky, A series of approximation algorithms for the acyclic directed steiner tree problem, Algorithmica 18 (1997) 99-110.
[103]A. Zhang, Y. Jiang, and Z. Tan, Online parallel machines scheduling with two hier-archies, Theoretical Computer Science 410 (2009) 3597-3605.
[104]C. Zhang, G. Wang, X. Liu, and J. Liu, Approximating scheduling machines with capacity constraints, in Proceedings of the 3rd International Workshop on Frontiers in Algorithmics,2009,283-292.
[105]Y. Zhang, J. Ren, and C. Wang, Scheduling with rejection to minimize the makespan. In Proceedings of the 3rd Annual International Conference on Combinatorial Optimiza-tion and Applications (COCOA),2009,411-420.
[106]周萍,蒋义伟,何勇,有两个服务等级的平行机排序问题,高校应用数学学报22(2007)275-284.