Search

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. [ABSTRACT FROM AUTHOR]