|
|
Algorithm Engineering for
|
max planck institut
informatik
informatik
|
|
|
Algorithm Engineering for
|
This project is funded by the DFG Priority Programme Algorithm Engineering.
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 will also be a part of our work.
Benjamin Doerr, MPII, Saarbrücken
Magnus Wahlström, MPII, Saarbrücken
Tobias Friedrich, International Computer Science Institute, Berkeley, California
Anna Huber, MPII, Saarbrücken
Marvin Künnemann, Saarland University, Saarbrücken
As our first new results within the project, we presented the first derandomization of Srinivasan's procedure (Sri01) for creating randomized roundings satisfying a hard constraint. We also presented an improved derandomization for B. Doerr's procedure (Doe06) for the same problem, improving on its error bound both theoretically and practically behaviour. We implemented all three methods (Raghavan, Srinivasan, Doerr), in randomized and derandomized versionns, and performed an experimental evaluation comparing the methods. This work appeared in ALENEX 2009 (DW09). Another application of rounding under constraints which we have examined is the unbiased rounding of matrices (where one wants to round the entries of a matrix to some fix precision so that sums over rows and columns are preserved).
The work on creating low-discrepancy point sets has also proceeded. We have implemented the proposed methods (DGS05, DGKP08), and performed evaluations of them. This first version of the main approach is already competitive with established methods for its intended settings, and we are considering further improvements to it. We are also working on the difficult problem of computing or approximating the actual discrepancy of a given point set in a reasonable amount of time. The evaluation of the component-by-component method has been accepted for publication in the proceedings of Monte Carlo and Quasi-Monte Carlo Methods 2008 (DGW09); the evaluation of (DGS05) is under submission.
In a somewhat wider context of derandomization and bounded randomness, we have proposed and studied a quasirandom variant of the classical push model for disseminating information in networks (the so-called randomized rumor spreading problem). The expected time before all nodes are informed using this method matches the bound for the standard random model for any graph, and for some instance classes (very sparse random graphs) it is better. An experimental analysis confirmed the viability of the approach; see (DFKS09).