关键词: 负载均衡, 近似算法, 全范数

Abstract: The load balancing problem with hierarchical constraints is a special case of the unrelated parallel machine scheduling problem. When the objective is to minimize the l_p norm of the machine load vector, by exploiting the combinatorial properties of the considered problem and the convexity of objective function, this paper designs an all norm 2-approximation algorithm, which is combinatorial. When the number of machines and norm are fixed, this paper constructs an auxiliary instance, and analyzes the relationship of optimal values of original instance and auxiliary instance. Then, this paper uses the dynamic algorithm to find an optimal solution to the auxiliary instance and construct a corresponding solution to the original instance, whose objective value is very close to the optimal value. These results improve previous best results on time complexity.

Key words: load balancing, approximation algorithms, all norm