Martin Stefan Krejca
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Martin Stefan Krejca has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Tobias Friedrich
Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
16 shared publications - Benjamin Doerr
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris
14 shared publications - Marcus Pappik
Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
9 shared publications - Andreas Göbel
Hasso Plattner Institute University of Potsdam Potsdam Germany
8 shared publications - Carsten Witt
Technical University of Denmark
7 shared publications - Philipp Fischbeck
University of Potsdam
4 shared publications
Latest Publications
- 25 August 2026
- Published by Springer Nature
- p. 147-162
Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-Valued OneMax Function
- 25 August 2026
- Published by Springer Nature
- p. 147-162
Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-Valued OneMax Function
- Open Access
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 49-50
Hot of the Press: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in only sporadic tight runtime analyses existing. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark. From this, we prove a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n2), improving over the previous estimate of O(n2 log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(nk+1) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2, 3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Andre Opris: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm. International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8876–8884. [6].
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 49-50
Open AccessHot of the Press: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in only sporadic tight runtime analyses existing. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark. From this, we prove a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n2), improving over the previous estimate of O(n2 log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(nk+1) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2, 3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Andre Opris: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm. International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8876–8884. [6].
- Open Access
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 51-52
Hot off the Press: Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 51-52
Open AccessHot off the Press: Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
- Open Access
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 35-36
Hot off the Press: Proven Approximation Superiority of SPEA2 over NSGA-II
The SPEA2 and the NSGA-II are two of the most widely used dominance-based multi-objective evolutionary algorithms (MOEAs). While prior theoretical work established similar runtime guarantees for both, the differences in their selection mechanisms were not well understood from an approximation perspective. We provide the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability. Specifically, the steady-state SPEA2 computes an optimal spread of the OneMinMax Pareto front in O(μ2n log(μ;) log(n)) expected function evaluations. In contrast, the steady-state NSGA-II, when started near an optimal spread with just two sub-optimal gaps, fails to achieve optimality within polynomial time with overwhelming probability. This is the first result showing a provable qualitative gap between the approximation abilities of these two algorithms. This paper summarizes the work Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. International Joint Conference on Artificial Intelligence, IJCAI 2025. [1].
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 35-36
Open AccessHot off the Press: Proven Approximation Superiority of SPEA2 over NSGA-II
The SPEA2 and the NSGA-II are two of the most widely used dominance-based multi-objective evolutionary algorithms (MOEAs). While prior theoretical work established similar runtime guarantees for both, the differences in their selection mechanisms were not well understood from an approximation perspective. We provide the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability. Specifically, the steady-state SPEA2 computes an optimal spread of the OneMinMax Pareto front in O(μ2n log(μ;) log(n)) expected function evaluations. In contrast, the steady-state NSGA-II, when started near an optimal spread with just two sub-optimal gaps, fails to achieve optimality within polynomial time with overwhelming probability. This is the first result showing a provable qualitative gap between the approximation abilities of these two algorithms. This paper summarizes the work Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. International Joint Conference on Artificial Intelligence, IJCAI 2025. [1].
- 13 November 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 5
A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive
- 13 November 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 5
A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive
- Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 1, 108-116
Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 1, 108-116
Open AccessResistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
- Open Access
- 27 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 142-153
Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal
- 27 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 142-153
Open AccessPopulation Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal
- Open Access
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 15-16
Hot off the Press: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 15-16
Open AccessHot off the Press: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
- Open Access
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 25-26
Hot off the Press: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 25-26
Open AccessHot off the Press: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
- Open Access
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 23-24
Hot off the Press: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 23-24
Open AccessHot off the Press: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces