TY - GEN
T1 - Randomized rounding in the presence of a cardinality constraint
AU - Doerr, Benjamin
AU - Wahlström, Magnus
PY - 2009/1/1
Y1 - 2009/1/1
N2 - 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 de-randomized 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.
AB - 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 de-randomized 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.
UR - https://www.scopus.com/pages/publications/84959898443
M3 - Conference contribution
AN - SCOPUS:84959898443
T3 - 11th Workshop on Algorithm Engineering and Experiments and 6th Workshop on Analytic Algorithmics and Combinatorics 2009, ALENEX 2009/ANALCO 2009
SP - 162
EP - 174
BT - 11th Workshop on Algorithm Engineering and Experiments and 6th Workshop on Analytic Algorithmics and Combinatorics 2009, ALENEX 2009/ANALCO 2009
PB - Society for Industrial and Applied Mathematics Publications
T2 - 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009 and 6th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2009
Y2 - 3 January 2009
ER -