Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 DetailsÜbersicht
  Efficient Sampling Methods for Discrete Distributions

Bringmann, K., & Panagiotou, K. (2012). Efficient Sampling Methods for Discrete Distributions. In A. Czumaj, K. Mehlhorn, A. M. Pitts, & R. Wattenhofer (Eds.), Automata, Languages, and Programming (pp. 133-144). Berlin: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-BBDB-2 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0023-C092-3
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
2012ICALP.pdf (beliebiger Volltext), 307KB
 
Datei-Permalink:
-
Name:
2012ICALP.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:
Bringmann, Karl1, Autor           
Panagiotou, Konstantinos2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p_1,...,p_n. We consider the problem of sampling a subset, which includes the i-th event independently with probability p_i, and the problem of sampling from the distribution, where the i-th event has a probability proportional to p_i. For both problems we present on two different classes of inputs � sorted and general probabilities � efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2012
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.1007/978-3-642-31594-7_12
BibTex Citekey: BringmannP12
Anderer: Local-ID: 76C613922FECC644C1257AD300348137-BringmannP12
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 39th International Colloquium on Automata, Languages, and Programming
Veranstaltungsort: Warwick, UK
Start-/Enddatum: 2012-07-09 - 2012-07-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Automata, Languages, and Programming
  Kurztitel : ICALP 2012
  Untertitel : 39th International Colloquium, ICALP 2012
Genre der Quelle: Konferenzband
 Urheber:
Czumaj, Artur1, Herausgeber           
Mehlhorn, Kurt1, Herausgeber           
Pitts, Andrew M.2, Herausgeber
Wattenhofer, Roger2, Herausgeber
Affiliations:
1 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
2 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 133 - 144 Identifikator: ISBN: 978-3-642-31593-0

Quelle 2

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