Algorithm Engineering for Randomized Rounding Procedures
Prof. Dr. Benjamin Doerr; Max-Planck-Institut für Informatik, Saarbrücken
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.
- M. Gnewuch, M. Wahlström and C. Winzen. "A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting", SIAM J. Numerical Analysis, Vol. 50. 2012, pp. 781-807. [More]
- P. Giannopoulos, C. Knauer, M. Wahlström and D. Werner. "Hardness of discrepancy computation and -net verification in high dimension", J. Complexity, Vol. 28. 2012, pp. 162-176. [More]
- B. Doerr, M. Fouz and T. Friedrich. "Asynchronous Rumor Spreading in Preferential Attachment Graphs". SWAT. 2012. pp. 307-315. [More]
- B. Doerr, M. Fouz and T. Friedrich. "Why rumors spread so quickly in social networks", Commun. ACM, Vol. 55. 2012, pp. 70-75. [More]
- B. Doerr, M. Künnemann and M. Wahlström. "Dependent Randomized Rounding: The Bipartite Case". ALENEX. 2011. pp. 96-106. [More]