214 citations · 292 across the 6 of their papers we have counts for
6 papers
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…
Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
Carola Doerr, G. Ramakrishna, Jens M. Schmidt
We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two.…
A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy
Michael Gnewuch, Magnus Wahlström, Carola Winzen
We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. An…
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…