English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Unbiased Rounding of Rational Matrices

Doerr, B., & Klein, C. (2006). Unbiased Rounding of Rational Matrices. In FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference (pp. 200-211). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2465-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2467-6
Genre: Conference Paper

Files

show Files
hide Files
:
unbiasmatr2006.pdf (Any fulltext), 221KB
 
File Permalink:
-
Name:
unbiasmatr2006.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-
:
paper.pdf (Any fulltext), 98KB
 
File Permalink:
-
Name:
paper.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Doerr, Benjamin1, Author           
Klein, Christian1, Author           
Arun-Kumar, S., Editor
Garg, Naveen1, Editor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-03-172006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314504
Other: Local-ID: C1256428004B93B8-1FFC886090FF93A5C1257230004364EF-unbiasmatr2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Kolkata, India
Start-/End Date: 2006-12-13

Legal Case

show

Project information

show

Source 1

show
hide
Title: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 200 - 211 Identifier: ISBN: 978-3-540-49994-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4337 Sequence Number: - Start / End Page: - Identifier: -