• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 计算机网络与信息安全 • 上一篇    下一篇

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

关莉,冯彦雪   

  1. (云南大学数学与统计学院,云南 昆明 650500)
  • 收稿日期:2019-06-11 修回日期:2019-08-13 出版日期:2019-11-25 发布日期:2019-11-25
  • 基金资助:

    国家自然科学基金(11761078,11861075);云南省教育厅科学研究基金(2017ZZX235);云南省高校计算理论与应用科技创新团队建设项目(云教高[2018]134号);云南省科技厅-云南大学联合基金重点项目(2018FY001(-014))

A mixed ring loading problem with penalty cost

GUAN Li,FENG Yan-xue   

  1. (School of Mathematics and Statistics,Yunnan University,Kunming 650500,China)
  • Received:2019-06-11 Revised:2019-08-13 Online:2019-11-25 Published:2019-11-25

摘要:

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

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

Abstract:

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  rj has a demand  dj and a penalty pj. When the request  rj is accepted, its traffic can be transmitted along the ring clockwise and counter clockwise. When the request   rj is rejected, the penalty   pj 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.
 

Key words: approximation algorithms, mixed cycle loading, penalty cost