Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.cse.iitd.ernet.in/~fsttcs26/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 01:16:07 PM
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