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 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.
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 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.
U2 - 10.1137/1.9781611972894.16
DO - 10.1137/1.9781611972894.16
M3 - Conference contribution
AN - SCOPUS:77956518496
SN - 9780898719307
T3 - 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009
SP - 162
EP - 174
BT - 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009
PB - Society for Industrial and Applied Mathematics Publications
T2 - 11th Annual Workshop on Algorithm Engineering and Experiments, ALENEX 2009
Y2 - 3 January 2009 through 3 January 2009
ER -