The cyclical scheduling problem

We consider the (n−2,n)(n−2,n) cyclical scheduling problem which assigns a shift of n−2n−2 consecutive periods among a total of n periods to workers. We solve this problem by solving a series of b-matching problems on a cycle of n   vertices. Each vertex has a capacity, and edges have costs associated with them. The objective is to maximize the total cost of the matching. The best known algorithm for this problem uses network flow, which runs in O(n2log⁡n)O(n2log⁡n) on a cycle. We provide an O(nlog⁡n)O(nlog⁡n) algorithm for this problem. Using this, we provide an O(nlog⁡nlog⁡nbmax)O(nlog⁡nlog⁡nbmax) algorithm for the (n−2,n)(n−2,n) cyclical scheduling problem, where bmaxbmax is the maximum capacity on a vertex.