线上期刊服务咨询,发表咨询:400-808-1701 订阅咨询:400-808-1721

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

关莉; 冯彦雪 计算机工程与科学 2019年第11期

摘要:在过去的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是一个固定的常数。

关键词:近似算法混合环负载惩罚费用

单位:云南大学数学与统计学院; 云南昆明650500

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

计算机工程与科学

北大期刊

¥624.00

关注 46人评论|5人关注