Access Restriction

Author Doerr, Benjamin ♦ Wahlstrm, Magnus
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Randomized rounding ♦ Algorithm engineering ♦ Approximation algorithms
Abstract We consider the problem of generating randomized roundings that satisfy a single cardinality constraint and admit Chernoff-type large deviation bounds for weighted sums of the variables. That this can be done efficiently was proven by Srinivasan [2001], a different approach was later given by the first author [Doerr 2006]. In this work, we (a) present an improved version of the bitwise derandomization given by Doerr, (b) give the first derandomization of Srinivasan's tree-based randomized approach and prove its correctness, and (c) experimentally compare the resulting algorithms. Our experiments show that adding a single cardinality constraint typically reduces the rounding errors and only moderately increases the running times. In general, our derandomization of the tree-based approach is superior to the derandomized bitwise one, while the two randomized versions produce very similar rounding errors. When implementing the derandomized tree-based approach, however, the choice of the tree is important.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-01-07
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 19
Page Count 18
Starting Page 1.1
Ending Page 1.18

Open content in new tab

   Open content in new tab
Source: ACM Digital Library