Passer à la navigation principale Passer à la recherche Passer au contenu principal

How to generate randomized roundings with dependencies and how to derandomize them

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collectionChapitreRevue par des pairs

Résumé

We give a brief survey on how to generate randomized roundings that satisfy certain constraints with probability one and how to compute roundings of comparable quality deterministically (derandomized randomized roundings). The focus of this treatment of this broad topic is on how to actually compute these randomized and derandomized roundings and how the different algorithms with similar proven performance guarantees compare in experiments and the applications of computing low-discrepancy point sets, low-congestion routing, the max-coverage problem in hypergraphs, and broadcast scheduling. While mostly surveying results of the last 5 years, we also give a simple, unified proof for the correctness of the different dependent randomized rounding approaches.

langue originaleAnglais
titreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditeurSpringer Verlag
Pages159-184
Nombre de pages26
Les DOIs
étatPublié - 1 nov. 2016

Série de publications

NomLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9220 LNCS
ISSN (imprimé)0302-9743
ISSN (Electronique)1611-3349

Empreinte digitale

Examiner les sujets de recherche de « How to generate randomized roundings with dependencies and how to derandomize them ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation