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

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)

- Three programs for the exact computation of the star discrepancy of a set of points: discr_calc.tar.gz. In particular, contains an implementation of the Dobkin-Eppstein-Mitchell algorithm.
- TA_algs.tar.gz -- Programs for estimating (lower-bounding) the star discrepancy, implementing
`TA_basic`and`TA_improved`from (GWW12) (arXiv preprint). - Routines for creating (randomized or derandomized) dependent roundings subject to various constraints available upon request. Contact Magnus Wahlström (wahl at mpi-inf etc).
- A proper "rounding library" is being developed. We welcome opinions on usability!

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.

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

- (DFF12a) B. Doerr, M. Fouz, and T. Friedrich:
**Asynchronous Rumor Spreading in Preferential Attachment Graphs**. In*Proceedings of SWAT 2012*, pages 307-315. - (DFF12b) B. Doerr, M. Fouz, and T. Friedrich:
**Why rumors spread so quickly in social networks**. Communications of the ACM, 55(6):70-75, 2012. - (GKWW12) P. Giannopoulos, C. Knauer, M. Wahlström, and D. Werner:
**Hardness of discrepancy computation and epsilon-net verification in high dimension**. Journal of Complexity, 28(2):162-176, 2012. Online preprint. - (GWW12) M. Gnewuch, M. Wahlström, and C. Winzen:
**A New Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy**. SIAM Journal of Numerical Analysis, 50(2):781-807, 2012. Online preprint. - (DF11a) B. Doerr and M. Fouz:
**Asymptotically Optimal Randomized Rumor Spreading.**In*Proceedings of ICALP 2011*, pages 502-513. - (DF11b) B. Doerr and M. Fouz:
**Quasi-random rumor spreading: Reducing randomness can be costly**. Information Processing Letters, 111(5):227-230, 2011. -
(DFF11) B. Doerr, M. Fouz, and T. Friedrich:
**Social Networks Spread Rumors in Sublogarithmic Time.**In*Proceedings of STOC 2011*, pages 21-30. - (DFKS11) B. Doerr, T. Friedrich, M. Künnemann, and T. Sauerwald:
**Quasirandom rumor spreading: An experimental analysis.**Journal of Experimental Algorithmics 16, 2011 (special issue on ALENEX 2009; journal version of (DFKS09)). - (DKW11) B. Doerr, M. Künnemann, M. Wahlstr&oum;m:
**Dependent Randomized Rounding: The Bipartite Case**(PDF). ALENEX 2011, pp. 69-106, 2011. -
(DKW10) B. Doerr, M. Künnemann, M. Wahlström:
**Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.**In*Proceedings of SEA 2010*, pages 190-210. - (DGW10) B. Doerr, M. Gnewuch, M. Wahlström:
**Algorithmic Construction of Low-Discrepancy Point Sets via Dependent Randomized Rounding.**Journal of Complexity, 26(5):490-507, 2010. -
(DFS09) B. Doerr, T. Friedrich, T. Sauerwald:
**Quasirandom rumor spreading: expanders, push vs. pull, and robustness.**In*Proceedings of ICALP 2009*. -
(DFKS09) B. Doerr, T. Friedrich, M. Künnemann, T. Sauerwald:
**Quasirandom Rumor Spreading: An Experimental Analysis.**In*Proceedings of ALENEX 2009*, pages 145-153. -
(DGW09) B. Doerr, M. Gnewuch, M. Wahlström:
**Implementation of a component-by-component algorithm to generate small low-discrepancy samples.**Monte Carlo and Quasi-Monte Carlo Methods 2008, pages 323-338. -
(DW09) B. Doerr, M. Wahlström:
**Randomized Rounding in the Presence of a Cardinality Constraint.**In*Proceedings of ALENEX 2009*, pages 162-174. -
(DGKP08)
B. Doerr, M. Gnewuch, P. Kritzer, F. Pillichshammer:
**Component-by-component construction of low-discrepancy point sets of small size.**Monte Carlo Methods and Applications, 14 (2008), 129-149. -
(DFS08)
B. Doerr, T. Friedrich, T. Sauerwald:
**Quasirandom Rumor Spreading.**In*Proceedings of SODA'08*, pages 773-781, 2008. -
(FDKO07)
T. Friedrich, B. Doerr, C. Klein, R. Osbild:
**Unbiased Matrix Rounding.***Electronic Notes in Discrete Mathematics*28, pages 41-46, 2007.

- (BA99) A.-L. Barabási and R. Albert:
**Emergence of scaling in random networks.***Science*286: 509-512 (October 1999).