Algorithmic Aspects of Divisor-Based Biproportional Rounding

Biproportional rounding of a matrix is the problem of assigning values to the elements of a matrix that are proportional to a given input matrix. The assignment should be integral and fulfill a set of rowand column-sum requirements. In a divisor-based method the problem is solved by computing appropriate rowand column-divisors, and by rounding the quotients. The only known divisor-based method that provably solves the problem is the tie-and-transfer algorithm by Balinski, Demange and Rachev. We analyze the complexity of this algorithm, and show that it is pseudo-polynomial. Two different approaches for reducing the complexity to (weakly) polynomial are presented. Finally, we give efficient algorithms for identifying ties, quotient intervals and divisor intervals.