混合环上带惩罚费用的负载平衡问题

A mixed ring loading problem with penalty cost

在过去的20多年里,环负载平衡问题得到了广泛的研究。带惩罚费用的环负载平衡问题是环负载平衡问题的推广形式,在无向环和有向环上有一些研究结果。提出了带惩罚费用的混合环负载平衡问题,对于给定的混合环C和点对集,每1个点对r j都有1个流量d j和1个惩罚费用p j,当点对r j被接收时,其流量可以沿环上的顺时针路和逆时针路进行运输,点对r j也可以被拒绝,此时将产生惩罚费用p j,目标是使得环C上连接边的最大负载和惩罚费用之和达到最小。在流量可分的情况下,利用线性规划取整技巧,给出了1个2-近似算法,进一步地,利用随机取整技巧,得到1个更好的近似算法,近似比为1.58。类似地,在流量不可分的情况下,给出了1个3-近似算法和1个(1.58+ε)-近似算法,其中ε>0是一个固定的常数。

In the past more than 20 years,the ring loading problem has been studied widely.The ring loading problem with penalty cost is the generalized form of the ring loading problem.There are some research results on undirected rings and directed rings.This paper proposes a mixed ring loading problem with penalty cost.Given a mixed ring C and a set of requests,each request r j has a demand d j and a penalty p j.When the request r j is accepted,its traffic can be transmitted along the ring clockwise and counter clockwise.When the request r j is rejected,the penalty p j is generated to minimize the sum of the maximum load among all links on the ring and the total penalty cost of the rejected requests.When the demand can be split,a 2-approximation algorithm is given by using the LP-rounding technique.Further,a 1.58-approximation algorithm is obtained by using the random rounding technique.Similarly,when the demand cannot be split,a 3-approximation algorithm and a(1.58+ε)-approximation algorithm are given,whereε>0 is a constant.