An efficient algorithm for the ring loading problem with integer demand splitting

In the ring loading problem, traffic. demands are given for each pair of no des in an undirected ring network and a flow is routed in either of two dir ections, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to mi nimize the maximum load on the ring. Myung [J. Korean OR and MS Society, 23 (1998), pp. 49-62 (in Korean)] has presented an efficient algorithm for so lving a problem where flow is restricted to integers. However, the proof fo r the validity of the algorithm in their paper is long and complicated and as the paper is written in Korean, its accessibility is very limited. In th is paper, we slightly modify their algorithm and provide a simple proof for the correctness of the proposed algorithm.