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: Goto entry point

 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:

 (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
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