# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Unbiased Rounding of Rational Matrices

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Doerr, B., & Klein, C. (2006). Unbiased Rounding of Rational Matrices. In *FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference*
(pp. 200-211). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2465-A

##### Abstract

Rounding a real-valued matrix to an integer one such that the rounding errors
in all rows and columns are less than one is a classical problem.
It has been applied to hypergraph coloring, in scheduling and in statistics.
Here, it often is also desirable to round each entry randomly such that the
probability of rounding it up equals its fractional part.
This is known as unbiased rounding in statistics and as randomized rounding in
computer science.
We show how to compute such an unbiased rounding of an $m \times n$ matrix in
expected time $O(m n q^2)$, where $q$ is the common denominator of the matrix
entries.
We also show that if the denominator can be written as $q=\prod_{i=1}^\ell q_i$
for some integers $q_i$, the expected runtime can be reduced to $O(m n
\sum_{i=1}^\ell q_i^2)$.
Our algorithm can be derandomised efficiently using the method of conditional
probabilities.
Our roundings have the additional property that the errors in all initial
intervals of rows and columns are less than one.