How to Generate Randomized Roundings with Dependencies and How to Derandomize Them

Benjamin Doerr, Magnus Wahlström

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review


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.
Original languageEnglish
Title of host publicationAlgorithm Engineering: Selected Results and Surveys
Number of pages26
ISBN (Electronic)978-3-319-49487-6
ISBN (Print)978-3-319-49486-9
Publication statusPublished - 11 Nov 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
ISSN (Print)0302-9743

Cite this