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

Computer Engineering & Science

Previous Articles     Next Articles

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

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