We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as defined by Barabasi and Albert) in time \(O(\sqrt\log n})\) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be \(\Theta(\log n / \log\log n)\).
2006
Ajwani, Deepak; Friedrich, Tobias; Meyer, UlrichAn \(O(n^{2.75})\) Algorithm for Online Topological Ordering. Scandinavian Workshop on Algorithm Theory (SWAT) 2006: 53-64
We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in \(O(n^{2.75})\) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of \(O(\min(m^3/2 \log n, m^3/2 + n^2 \log n)\) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting.
Doerr, Benjamin; Friedrich, Tobias; Klein, Christian; Osbild, RalfUnbiased Matrix Rounding. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2006: 102-112
We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size \(m \times n\), we reduce the runtime from \(O((mn)^2)\) to \(O(mn \log(mn))\). Second, our roundings also have a rounding error of less than one in all initial intervals of rows and columns. Consequently, arbitrary intervals have an error of at most two. This is particularly useful in the statistics application of controlled rounding. The same result can be obtained via (dependent) randomized rounding. This has the additional advantage that the rounding is unbiased, that is, for all entries \(y_{ij}\) of our rounding, we have \(E(y_{ij}) = x_{ij}\), where \(x_{ij}\) is the corresponding entry of the input matrix.
Algorithm Engineering
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.