MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Friedrich, Tobias
Klein, Christian
Osbild, Ralf		dblp
dblp
dblp
dblp
Editor(s):
Arge, Lars
Freivalds, Rusins		dblp
dblp
Not MPII Editor(s):
Arge, Lars
Freivalds, Rusins
BibTeX cite key*:
DFKO06
Title, Booktitle
Title*:
Unbiased Matrix Rounding
Booktitle*:
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory
Event, URLs
Conference URL::
http://www.lumii.lv/swat
Downloading URL:
Event Address*:
Riga, Latvia
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 July 2006
Event End Date:
8 July 2006
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4059
Number:
Month:
Pages:
102-112
Year*:
2006
VG Wort Pages:
26
ISBN/ISSN:
978-3-540-35753-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We show several ways to round a real matrix to an integer one in such a way 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 $m \times n$ matrices, we reduce the runtime from $O( (m n)^2 ) $ to $O(m n \log(m n))$. 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 $y_{ij}$ of our rounding, we have $E(y_{ij}) = x_{ij}$, where $x_{ij}$ is the corresponding entry of the input matrix.
Download
Access Level:
MPG

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
not specified
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DFKO06,
AUTHOR = {Doerr, Benjamin and Friedrich, Tobias and Klein, Christian and Osbild, Ralf},
 EDITOR = {Arge, Lars and Freivalds, Rusins},
 TITLE = {Unbiased Matrix Rounding},
 BOOKTITLE = {Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4059},
 PAGES = {102--112},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Riga, Latvia},
 ISBN = {978-3-540-35753-7},
}

Entry last modified by Regina Kraemer, 04/11/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Tobias Friedrich		Created
04/01/2006 15:28:09
Revisions
15.
14.
13.
12.
11.		Editor(s)
Regina Kraemer
Regina Kraemer
Benjamin Doerr
Christine Kiesel
Christine Kiesel		Edit Dates
04/11/2007 10:55:28 AM
04/11/2007 10:51:17 AM
03/17/2007 04:06:58 PM
01.02.2007 08:43:36
01.02.2007 08:40:53