Load Balancing And Optimization Problems

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.