@inproceedings{e6b74a14295a419eae0e738a7e3fa25c,
title = "Unbiased matrix rounding",
abstract = "We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size m x n, we reduce the runtime from O((mn)2) to O(mn log(mn)). Second, our roundings also have a rounding error of less than one in all initial intervals of rows and columns. Consequently, arbitrary intervals have an error of at most two. This is particularly useful in the statistics application of controlled rounding. The same result can be obtained via (dependent) randomized rounding. This has the additional advantage that the rounding is unbiased, that is, for all entries yij of our rounding, we have E(yij) = Xij, where Xij is the corresponding entry of the input matrix.",
author = "Benjamin Doerr and Tobias Friedrich and Christian Klein and Ralf Osbild",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11785293\_12",
language = "English",
isbn = "354035753X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "102--112",
booktitle = "Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings",
note = "10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 ; Conference date: 06-07-2006 Through 08-07-2006",
}