In the ring loading problem, traffic demands are given for each pair of nodes in an undirected ring network with n nodes and a flow is routed in either of the two directions, clockwise and counter-clockwise. The load of a link is the sum of the flows routed through the link and the objective of the problem is to minimize the maximum load on the ring. In the ring loading problem with integer demand splitting, each demand can be split between the two directions and the flow routed in each direction is restricted to integers. Recently, Vachani et al. have developed an O(n3) algorithm for solving this integer version of the ring loading problem and independently. Schrijver et al. have presented an algorithm which solves the problem with {0, 1} demands in O(n2 | K |) time where K denotes the index set of the origin–destination pairs of nodes having flow demands. In this paper, we develop an algorithm which solves the problem in O(n | K |) time.
