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
- 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]
- B. Doerr and M. Fouz. "Asymptotically Optimal Randomized Rumor Spreading". ICALP. 2011. [More]
- B. Doerr, M. Fouz and T. Friedrich. "Social Networks Spread Rumors in Sublogarithmic Time". STOC. 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. Gnewuch and M. Wahlström. "Algorithmic construction of low-discrepancy point sets via dependent randomized rounding", Journal of Complexity, Vol. 26. 2010, pp. 490-507. [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]
- B. Doerr, M. Gnewuch and M. Wahlström. "Implementation of a Component-By-Component Algorithm to Generate Small Low-Discrepancy Samples". L. Ecuyer, Pierre, Owen and A. B. eds. Springer Berlin Heidelberg. 2009. pp. 323-338. [More]
- B. Doerr, T. Friedrich, M. Künnemann and T. Sauerwald. "Quasirandom Rumor Spreading: An Experimental Analysis". 10th Workshop on Algorithm Engineering and Experiments (ALENEX). 2009. pp. 145-153. [More]
- B. Doerr, T. Friedrich and T. Sauerwald. "Quasirandom Rumor Spreading: Expanders, Push vs.\ Pull, and Robustness". 36th International Colloquium on Automata, Languages and Programming (ICALP). 2009. pp. 366-377. [More]
- B. Doerr and M. Wahlström. "Randomized Rounding in the Presence of a Cardinality Constraint". 10th Workshop on Algorithm Engineering and Experiments (ALENEX). 2009. pp. 162-174. [More]
- B. Doerr, M. Gnewuch, P. Kritzer and F. Pillichshammer. "Component-by-component construction of low-discrepancy point sets of small size", Monte Carlo Methods and Applications, Vol. 14. 2008, pp. 129-149. [More]
- B. Doerr, T. Friedrich and T. Sauerwald. "Quasirandom Rumor Spreading". 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2008. pp. 773-781. [More]