214 citations · 292 across the 6 of their papers we have counts for
4 papers · 1 filter
Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
Benjamin Doerr, Amirhossein Rajabi, Carsten Witt
We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial…
Ranking-Based Black-Box Complexity
Benjamin Doerr, Carola Winzen
Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing the…
Multiplicative Drift Analysis
Benjamin Doerr, Daniel Johannsen, Carola Winzen
In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multipl…
Optimizing Monotone Functions Can Be Difficult
Benjamin Doerr, Thomas Jansen, Dirk Sudholt +2
Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly m…