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

Abstract

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
PublisherSpringer
Pages159-184
Number of pages26
Volume9220
ISBN (Electronic)978-3-319-49487-6
ISBN (Print)978-3-319-49486-9
DOIs
Publication statusPublished - 11 Nov 2016

Publication series

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

Cite this