TY - BOOK

T1 - Algorithmic Aspects of Divisor-Based Biproportional Rounding

AU - Zachariasen, Martin Tvede

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

M3 - Commissioned report

T3 - Technical report

BT - Algorithmic Aspects of Divisor-Based Biproportional Rounding

PB - University of Copenhagen

ER -