Algorithmic Aspects of Divisor-Based Biproportional Rounding

Research output: Book/ReportCommissioned reportpeer-review


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.
Original languageEnglish
PublisherUniversity of Copenhagen
Number of pages22
Publication statusPublished - 2006

Publication series

NameTechnical report
ISSN (Electronic)0107-8283


Dive into the research topics of 'Algorithmic Aspects of Divisor-Based Biproportional Rounding'. Together they form a unique fingerprint.

Cite this