Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2465-A Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2467-6
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
unbiasmatr2006.pdf (beliebiger Volltext), 221KB
 
Datei-Permalink:
-
Name:
unbiasmatr2006.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
paper.pdf (beliebiger Volltext), 98KB
 
Datei-Permalink:
-
Name:
paper.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Doerr, Benjamin1, Autor           
Klein, Christian1, Autor           
Arun-Kumar, S., Herausgeber
Garg, Naveen1, Herausgeber           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-03-172006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 314504
Anderer: Local-ID: C1256428004B93B8-1FFC886090FF93A5C1257230004364EF-unbiasmatr2006
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Kolkata, India
Start-/Enddatum: 2006-12-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 200 - 211 Identifikator: ISBN: 978-3-540-49994-7

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4337 Artikelnummer: - Start- / Endseite: - Identifikator: -