Algorithm Engineering for Randomized Rounding Procedures
Description
Prof. Dr. Benjamin Doerr; Max-Planck-Institut für Informatik, Saarbrücken
Project website
Randomized rounding is one of the core methods of randomized computation, and is at the heart of many algorithms with good theoretical properties. However, despite this, and despite the long roots of the theoretical method, it seems that the performance of the method has scarcely ever been empirically evaluated, and implementations of the method are found only in isolated special cases.
Moreover, recent theoretical developments have extended the range of applicability of the method to include further ranges of problems, such as the problem of multi-commodity flow, by providing methods of rounding which allow certain conditions (so-called hard constraints) to be maintained with a guarantee. Different approaches have been suggested for this, in some situations without any obvious a priori indications of one being preferable to the other, making the need for empirical evaluations and comparisons stronger.
One aim of the project is thus to provide these much-needed empirical evaluations, comparing the methods both to one another and to other suggested methods (not of the randomized rounding type); another is to, based on the outcome of this, further the implementation and design of rounding algorithms to practical maturity.
One particular application where randomized rounding tools have seen some recent use is the creation of good sets of sampling points ( low-discrepancy point sets) in the high-dimensional unit cube, which is needed in e.g. numerical integration problems. This topic is also part of our work.
Publications
- B. Doerr, M. Künnemann and M. Wahlström. "Dependent Randomized Rounding: The Bipartite Case". ALENEX. 2011. pp. 96-106. [More]
- B. Doerr, M. Fouz and T. Friedrich. "Social Networks Spread Rumors in Sublogarithmic Time". STOC. 2011. [More]
- B. Doerr and M. Fouz. "Asymptotically Optimal Randomized Rumor Spreading". ICALP. 2011. [More]
- B. Doerr, T. Friedrich, M. Künnemann and T. Sauerwald. "Quasirandom Rumor Spreading: An Experimental Analysis", Journal of Experimental Algorithmics. 2011. [More]
- B. Doerr, M. Künnemann and M. Wahlström. "Randomized Rounding for Routing and Covering Problems: Experiments and Improvements". SEA. 2010. pp. 190-201. [More]