Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
196
result(s) for
"Doerr, Benjamin"
Sort by:
Deterministic Random Walks on the Two-Dimensional Grid
Jim Propp's rotor–router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbours in a fixed order. We analyse the difference between the Propp machine and random walk on the infinite two-dimensional grid. It is known that, apart from a technicality, independent of the starting configuration, at each time the number of chips on each vertex in the Propp model deviates from the expected number of chips in the random walk model by at most a constant. We show that this constant is approximately 7.8 if all vertices serve their neighbours in clockwise or order, and 7.3 otherwise. This result in particular shows that the order in which the neighbours are served makes a difference. Our analysis also reveals a number of further unexpected properties of the two-dimensional Propp machine.
Journal Article
Theory of randomized search heuristics
Randomized search heuristics such as evolutionary algorithms, genetic algorithms, evolution strategies, ant colony and particle swarm optimization turn out to be highly successful for optimization in practice. The theory of randomized search heuristics, which has been growing rapidly in the last five years, also attempts to explain the success of the methods in practical applications.
eBook
Playing Mastermind with Constant-Size Memory
We analyze the classic board game of Mastermind with
n
holes and a constant number of colors. The classic result of Chvátal (Combinatorica 3:325–329,
1983
) states that the codebreaker can find the secret code with
Θ
(
n
/log
n
) questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory Comput. Syst. 39:525–544,
2006
) on the memory-restricted black-box complexity of the OneMax function class.
Journal Article
Detecting structural breaks in time series via genetic algorithms
Detecting structural breaks is an essential task for the statistical analysis of time series, for example, for fitting parametric models to it. In short, structural breaks are points in time at which the behaviour of the time series substantially changes. Typically, no solid background knowledge of the time series under consideration is available. Therefore, a black-box optimization approach is our method of choice for detecting structural breaks. We describe a genetic algorithm framework which easily adapts to a large number of statistical settings. To evaluate the usefulness of different crossover and mutation operations for this problem, we conduct extensive experiments to determine good choices for the parameters and operators of the genetic algorithm. One surprising observation is that use of uniform and one-point crossover together gave significantly better results than using either crossover operator alone. Moreover, we present a specific fitness function which exploits the sparse structure of the break points and which can be evaluated particularly efficiently. The experiments on artificial and real-world time series show that the resulting algorithm detects break points with high precision and is computationally very efficient. A reference implementation with the data used in this paper is available as an applet at the following address:
http://www.imm.dtu.dk/~pafi/TSX/
. It has also been implemented as package SBRect for the statistics language R.
Journal Article
The hereditary discrepancy is nearly independent of the number of colors
We investigate the discrepancy (or balanced coloring) problem for hypergraphs and matrices in arbitrary numbers of colors. We show that the hereditary discrepancy in two different numbers a,b∈N≥2a, b \\in {\\mathbb N} _{\\ge 2} of colors is the same apart from constant factors, i.e., \\[ herdisc(⋅,b)=Θ(herdisc(⋅,a)).\\operatorname {herdisc}(\\cdot ,{b}) = \\Theta ( \\operatorname {herdisc}(\\cdot ,{a})). \\] This contrasts the ordinary discrepancy problem, where no correlation exists in many cases.
Journal Article
Simple and optimal randomized fault-tolerant rumor spreading
We revisit the classic problem of spreading a piece of information in a group of
n
fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903–912,
1996
), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of
O
(
log
n
)
when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization).
Journal Article
Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm.
Paper
A Sharp Discrepancy Bound for Jittered Sampling
For \\(m, d \\in {\\mathbb N}\\), a jittered sampling point set \\(P\\) having \\(N = m^d\\) points in \\([0,1)^d\\) is constructed by partitioning the unit cube \\([0,1)^d\\) into \\(m^d\\) axis-aligned cubes of equal size and then placing one point independently and uniformly at random in each cube. We show that there are constants \\(c \\ge 0\\) and \\(C\\) such that for all \\(d\\) and all \\(m \\ge d\\) the expected non-normalized star discrepancy of a jittered sampling point set satisfies \\[c \\,dm^{\\frac{d-1}{2}} \\sqrt{1 + \\log(\\tfrac md)} \\le {\\mathbb E} D^*(P) \\le C\\, dm^{\\frac{d-1}{2}} \\sqrt{1 + \\log(\\tfrac md)}.\\] This discrepancy is thus smaller by a factor of \\(\\Theta\\big(\\sqrt{\\frac{1+\\log(m/d)}{m/d}}\\,\\big)\\) than the one of a uniformly distributed random point set of \\(m^d\\) points. This result improves both the upper and the lower bound for the discrepancy of jittered sampling given by Pausinger and Steinerberger (Journal of Complexity (2016)). It also removes the asymptotic requirement that \\(m\\) is sufficiently large compared to \\(d\\).
Paper