A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting

We are given an n-node undirected ring network, in which each link of the ring is associated with a weight. Traffic demand is given for each pair of nodes in the ring. Each demand is allowed to be split into two integer parts, which are then routed in different directions, clockwise and counterclockwise, respectively. The load of a link is the sum of the flows routed through the link and the nonnegative weighted load of a link is the product of its weight and its load. The objective is to find a routing scheme such that the maximum weighted load on the ring is minimized. Based on some useful structural properties of the decision version of the problem, we design a polynomial-time combinatorial algorithm for the optimization problem.