MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Klein, Christian		dblp
dblp
Editor(s):
Arun-Kumar, S.
Garg, Naveen		dblp
dblp
Not MPII Editor(s):
Arun-Kumar, S.
BibTeX cite key*:
unbiasmatr2006
Title, Booktitle
Title*:
Unbiased Rounding of Rational Matrices
Booktitle*:
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference
Event, URLs
Conference URL::
http://www.cse.iitd.ernet.in/~fsttcs26/
Downloading URL:
Event Address*:
Kolkata, India
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
13 December 2006
Event End Date:
15 December 2006
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4337
Number:
Month:
Pages:
200-211
Year*:
2006
VG Wort Pages:
28
ISBN/ISSN:
3-540-49994-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://www.springerlink.com/content/b46030078764776p/
Download
Access Level:
Internal

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



BibTeX Entry:

@INPROCEEDINGS{unbiasmatr2006,
AUTHOR = {Doerr, Benjamin and Klein, Christian},
 EDITOR = {Arun-Kumar, S. and Garg, Naveen},
 TITLE = {Unbiased Rounding of Rational Matrices},
 BOOKTITLE = {FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4337},
 PAGES = {200--211},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Kolkata, India},
 ISBN = {3-540-49994-7},
}

Entry last modified by Anja Becker, 03/02/2010
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)
Mathias Bader		Created
11/24/2006 13:16:07
Revisions
12.
11.
10.
9.
8.		Editor(s)
Anja Becker
Uwe Brahm
Benjamin Doerr
Christine Kiesel
Christine Kiesel		Edit Dates
25.02.2008 08:49:12
07/07/2007 00:42:00
03/17/2007 04:08:33 PM
05.02.2007 20:26:37
05.02.2007 20:25:36