A faster algorithm for the ring loading problem with demand splitting

In the ring loading problem with demand splitting, traffic demands are given for each pair of nodes in an undirected ring network 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. The fastest algorithm to date is Myung. Kim and Tcha's algorithm that runs in O(n|K|) time where n is the number of nodes and K is the index set of the origin–destination pairs of nodes having flow traffic demands. Here we develop an algorithm for the ring loading problem with demand splitting that improves the rerouting step of Myung, Kim and Tcha's algorithm and runs in O(min{n|K|,n²}) time.