Randomized Rounding in the Presence of a Cardinality Constraint
Benjamin Doerr, Magnus Wahlström · Society for Industrial and Applied Mathematics eBooks · 2009
We regard the problem of generating randomized roundings with a single cardinality constraint. This is motivated by recent results of Srinivasan (FOCS 2001), Gandhi et al. (FOCS 2002, J. ACM 2006) and the first author (STACS 2005, STACS 2006). Our work results in (a) an improved version of the bitwise derandomization given by the first author, (b) the first derandomization of Srinivasan's tree-based randomized approach, together with a proof of its correctness, and (c) an experimental comparison of the resulting algorithms. Our experiments show that adding a single cardinality constraint typically reduces the rounding errors and not seriously 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.