Decoration   

Algorithm Engineering for
Randomized Rounding Procedures

max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Algorithm Engineering for Randomized Rounding Procedures

This project is funded by the DFG Priority Programme Algorithm Engineering.

Motivation

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.

Goals

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. Further, an area where randomized rounding is done without explicit mention, partially with dependencies, are randomized broadcasting algorithms building on the randomized rumor spreading paradigm. These topics will also be a part of our work.

Participants

Benjamin Doerr, MPII, Saarbrücken
Magnus Wahlström, MPII, Saarbrücken (post-doctoral researcher funded by the project)
Tobias Friedrich, MPII, Saarbrücken
Carola Winzen, MPII, Saarbrücken
Marvin Künnemann, Saarland University, Saarbrücken (student assistant funded by the project)

Software

Results in the second phase (Sept. 2009-Aug. 2011)

In the main, dependent rounding part of the project, there were several advancements. First, we extended the work started at ALENEX 2009 (DW09) by considering applications of dependent rounding with disjoint cardinality constraints to concrete approximation problems. We considered the problems of multi-commodity integer splittable flow and max coverage, both with algorithms suggested by Srinivasan (Sri01). Implementing and studying the approximation algorithms, we propose heuristic improvements to both for a better real-world performance, consisting of a modified LP solution for the flow problem, with solutions better suitable for rounding, and a greedy gradient rounding step for the max coverage problem to improve solution quality. Both modifications lead to significantly improved solution quality. This was published at SEA 2010 (DKW10). Second, we considered the bipartite graph rounding step of Gandhi et al. (GKPS06). For this case, as for the case of disjoint cardinality constraints, there are two distinctly different methods: that of Gandhi et al., building on Srinivasan (Sri01), and that of Doerr (Doe06). On a theoretical basis, the former method has a higher worst-case running time, while the latter has a larger constant in the error bound. However, these are theoretical statements, and it was not clear how overly pessimistic they were. In experiments, we find that there is a running time difference present, depending also on the graph structure, but that the difference is less pronounced than what theory would suggest. We give an improvement to Doerr's method, leading to identical error bounds as the method of Gandhi et al.; however, in experiments we detect a small but consistent remaining advantage in solution quality for the latter method. We also observe and implement a hybrid method that can unite the advantages of both methods. On the applications side, we consider the broadcast scheduling problem under various optimization goals, as suggested by Gandhi et al. (GKPS06). We provide full derandomizations of the approximation algorithms of Gandhi et al., and study the performance of the algorithms. The success is mixed: the full derandomizations perform clearly better than randomized or partially derandomized versions, and in one of the two goals (max throughput) the algorithm performs very well. However, in the min average delay setting, we find that for our data, all rounding-based algorithms are beaten by a simple greedy algorithm. This work was published at ALENEX 2011. Finally, to handle larger and more complex problems and instances, there were several improvements to code functionality, memory usage patterns, and execution speed.

In the low-discrepancy point set generation part of the project, we had previously encountered large difficulty in comparing the generated point sets, in that the tools available for computing or bounding the star discrepancy of a point set were clearly insufficient. In the second phase, to make future comparisons easier, we continued our work of providing better tools for computing and bounding the star discrepancy. We implemented the exact algorithm of Dobkin, Eppstein, and Mitchell (DEM96), and made the result freely available (see "software" above), and we are (in ongoing work) evaluating an improved method for lower bounds (GWW12).

The rumor spreading part of the project was also highly successful. Building on the quasi-random protocol suggested in (DFS08,DFS09), in (DF11a) we constructed a simple rumor spreading protocol for complete networks that has the asymptotically optimal run-time of $(1+o(1)) log_2(n)$ in $n$-node networks. This protocol thus is faster both than the quasirandom one using a larger number of dependencies and the classic, fully independent protocol. Seemingly, we found ``the right dose of randomness'' for this problem. We also analyzed randomized rumor spreading in real world network topologies (DFF11) as described by the preferential attachment model (BA99). Surprisingly, we here observe that the run-time decreases significantly if we choose the random communication partner uniformly at random, but excluding the neighbor contacted in the very previous round. This is a surprising gain caused by this minor modification of the protocol. Interestingly, such gains are not present in the network topologies usually investigated. It seems that real world networks react much more sensitive to such fine-tuning ideas.

Results in the first phase (Sept. 2007-Aug. 2009)

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 versions, 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) encountered some obstacles, in the form of the difficulty of computing the discrepancy, which made quality comparisons difficult, and in the form of the size of the generated rounding problems. Eventually, these obstacles were handled, and the evalution of (DGS05) was accepted for publication in the Journal of Complexity (DGW10).

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).

Publications

References