Carsten Witt

Professor

Address:		DTU Compute, Algorithms, Logic and Graphs, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Office:		Richard Petersens Plads, Building 322, Room 012
E-mail:
Phone:		+45 4525 3722
Fax:		+45 4593 0074
PGP:		Download public key

Research Interests: Theoretical aspects of randomized search heuristics, in particular evolutionary algorithms and estimation-of-distribution algorithms

PhD students:

Amirhossein Rajabi (graduated Aug. 23, 2022)
Christian Gießen (graduated Dec. 11, 2017)
Andrei Lissovoi (graduated March 16, 2016)

Current and past projects

Publications

Books

Frank Neumann and Carsten Witt (2010):
Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity
Natural Computing Series, Springer, ISBN 978-3-642-16543-6
Publisher's homepage: https://www.springer.com/978-3-642-16543-6
DOI: https://dx.doi.org/10.1007/978-3-642-16544-3

Book Chapters

Martin S. Krejca and Carsten Witt (2020):
Theory of Estimation-of-Distribution Algorithms
In B. Doerr and F. Neumann (Eds.): Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, Springer, pp. 405-442
arXiv preprint: https://arxiv.org/abs/1806.05392
Per Kristian Lehre and Carsten Witt (2013):
Finite First Hitting Time versus Stochastic Convergence in Particle Swarm Optimisation
In L. Di Gaspero, A. Schaerf, and T. Stützle (Eds.): Advances in Metaheuristics, Operations Research/Computer Science Interfaces Series 53, Springer, pp. 1-20
Preliminary version in Proceedings of MIC 2011
Extended technical report: https://arxiv.org/abs/1105.5540
Carsten Witt (2011):
Theory of Particle Swarm Optimization
In A. Auger and B. Doerr (Eds.): Theory of Randomized Search Heuristics, World Scientific Publishing, pp. 197-223
Frank Neumann, Dirk Sudholt and Carsten Witt (2009):
Computational Complexity of Ant Colony Optimization and its Hybridization with Local Search
In L.C. Jain, S. Dehuri, CP Lim (Eds.): Swarm Intelligence for Knowledge-Based Systems, Studies in Computational Intelligence (SCI) 248, pp. 91-120
DOI: https://dx.doi.org/10.1007/978-3-642-04225-6_6
Carsten Witt (2009):
Rigorous Runtime Analysis of Swarm Intelligence Algorithms - an Overview
In: C. Coello Coello, S. Dehuri and S. Ghosh (Eds.): Swarm Intelligence for Multi-objective Problems in Data Mining, Studies in Computational Intelligence (SCI) 242, Springer, pp. 157-177
DOI: https://dx.doi.org/10.1007/978-3-642-03625-5_7
Carsten Witt (2005):
Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung
In: Wagner et al. (Eds.): Ausgezeichnete Informatikdissertationen 2004, Gesellschaft für Informatik, Bonn, Germany, pp. 203-212

Editorial Work

Christian Igel, Dirk Sudholt, Carsten Witt (2017):
Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2017, Copenhagen, Denmark, January 12-15
ACM Press, ISBN 978-1-4503-4651-1
DOI: https://doi.acm.org/10.1145/3040718
Benjamin Doerr and Carsten Witt (2016):
Guest Editorial: Theory of Evolutionary Computation
Algorithmica, 75(3), pp. 425-427
DOI: https://dx.doi.org/10.1007/s00453-016-0157-4
Anne Auger and Carsten Witt (2012):
Theory of Randomized Search Heuristics
Algorithmica, 64(4), p. 621�622
DOI: https://dx.doi.org/10.1007/s00453-012-9686-7

Journal Articles

Frank Neumann and Carsten Witt (2025):
Fast Pareto Optimization Using Sliding Window Selectin for Problems with Deterministic and Stochastic Constraints
Evolutionary Computation, to appear
Frank Neumann and Carsten Witt (2025):
Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables
Evolutionary Computation, 33(2), pp. 191-214
DOI: https://doi.org/10.1162/evco_a_00355
Frank Neumann, Dirk Sudholt and Carsten Witt (2025):
The Compact Genetic Algorithm Struggles on Cliff Functions
Algorithmica, 87, pp. 507-536
DOI (Open Access): https://doi.org/10.1007/s00453-024-1281-w
Benjamin Doerr, Amirhossein Rajabi and Carsten Witt (2024):
Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Sapnning Tree Problem
Algorithmica, 86, pp. 64-89
DOI (Open Access): https://doi.org/10.1007/s00453-023-01135-x
Amirhossein Rajabi and Carsten Witt (2024):
Stagnation Detection in Highly Multimodal Fitness Landscapes
Algorithmica, 86, pp. 2929-2958
DOI (Open Access): https://doi.org/10.1007/s00453-024-01249-w
Carsten Witt (2023):
How Majority-Vote Crossover and Estimation-of-Distribution Algorithms Cope with Fitness Valleys
Theoretical Computer Science, 940(B), pp. 18-42
DOI (Open Access): https://doi.org/10.1016/j.tcs.2022.08.014
Amirhossein Rajabi and Carsten Witt (2023):
Stagnation Detection with Randomized Local Search
Evolutionary Computation, 31(1), pp. 1-29
DOI: https://doi.org/10.1162/evco_a_00313
Amirhossein Rajabi and Carsten Witt (2022):
Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
Algorithmica, 84(6), pp. 1694-1723
DOI: https://doi.org/10.1007/s00453-022-00933-z
Free view-only version: Springer Nature content sharing link
Pietro S. Oliveto, Dirk Sudholt and Carsten Witt (2022):
Tight Bounds on the Expected Runtime of a Standard Steady State Genetic Algorithm
Algorithmica, 84(6), pp. 1603-1658
DOI: https://doi.org/10.1007/s00453-021-00893-w
Dogan Corus, Andrei Lissovoi, Pietro Oliveto and Carsten Witt (2021):
On steady-state evolutionary algorithms and selective pressure: Why inverse rank-Based allocation of reproductive trials is best
ACM Transactions on Evolutionary Learning and Optimization, 1(1), pp. 1-38
DOI: https://doi.org/10.1145/3427474
Per Kristian Lehre and Carsten Witt (2021):
Tail bounds on hitting times of randomized search heuristics using variable drift analysis
Combinatorics, Probability and Computing, 30(4), pp. 550-569
DOI: https://doi.org/10.1017/S0963548320000565
Frank Neumann, Mojgan Pourhassan and Carsten Witt (2021):
Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint
Algorithmica, 83(10), pp. 3209-3237
DOI: https://doi.org/10.1007/s00453-020-00779-3
Andrew M. Sutton and Carsten Witt (2021):
Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs
Algorithmica, 83(10), pp. 3180-3208
DOI: https://doi.org/10.1007/s00453-020-00776-6
Johannes Lengler, Dirk Sudholt and Carsten Witt (2021):
The Complex Parameter Landscape of the Compact Genetic Algorithm
Algorithmica, 83, pp. 1096-1137
DOI: https://doi.org/10.1007/s00453-020-00778-4
Free view-only version: Springer Nature content sharing link
Benjamin Doerr, Carsten Witt and Jing Yang (2021):
Runtime Analysis for Self-adaptive Mutation Rates
Algorithmica, 83, pp. 1012-1053
DOI: https://doi.org/10.1007/s00453-020-00726-2
Free view-only version: Springer Nature content sharing link
Martin Krejca and Carsten Witt (2020):
Lower bounds on the run time of the Univariate Marginal Distribution Algorithm on OneMax
Theoretical Computer Science, 832(6), pp. 143-165
DOI: https://dx.doi.org/10.1016/j.tcs.2018.06.004
Benjamin Doerr, Christian Gießen, Carsten Witt and Jing Yang (2019):
The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate
Algorithmica, 81, pp. 593-631
DOI: https://doi.org/10.1007/s00453-018-0502-x
Free view-only version: Springer Nature content sharing link
Dirk Sudholt and Carsten Witt (2019):
On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization
Algorithmica, 81, pp. 1450-1489
DOI (open access): https://doi.org/10.1007/s00453-018-0480-z
Carsten Witt (2019):
Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax
Algorithmica, 81, pp. 632-667
DOI: https://dx.doi.org/10.1007/s00453-018-0463-0
Free view-only version: Springer Nature content sharing link
Andrei Lissovoi and Carsten Witt (2018):
The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization
Algorithmica, 80, pp. 1634-1657
DOI: https://dx.doi.org/10.1007/s00453-017-0377-2
Christian Gießen and Carsten Witt (2018):
Optimal Mutation Rates for the (1+λ) EA on OneMax Through Asymptotically Tight Drift Analysis
Algorithmica, 80, pp. 1710-1731
DOI: https://dx.doi.org/10.1007/s00453-017-0360-y
Free view-only version: Springer Nature content sharing link
Andrei Lissovoi and Carsten Witt (2017):
A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization
Algorithmica, 78, pp. 641-659
DOI: https://doi.org/10.1007/s00453-016-0262-4
Free view-only version: Springer Nature content sharing link
Christian Gießen and Carsten Witt (2017):
The Interplay of Population Size and Mutation Probability in the (1+λ) EA on OneMax
Algorithmica, 78, pp. 587-609
DOI: https://dx.doi.org/10.1007/s00453-016-0214-z
Free view-only version: Springer Nature content sharing link
Benjamin Doerr and Paul Fischer and Astrid Hilbert and Carsten Witt (2017):
Detecting Structural Breaks in Time Series via Genetic Algorithms
Soft Computing, 21, pp. 4707-4720
DOI: https://dx.doi.org/10.1007/s00500-016-2079-0
Free view-only version: Springer Nature content sharing link
Andrei Lissovoi and Carsten Witt (2016):
MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions
Algorithmica, 75(3), pp. 554-576
DOI: https://dx.doi.org/10.1007/s00453-015-9975-z
Free view-only version: Springer Nature content sharing link
Pietro S. Oliveto and Carsten Witt (2015):
Improved Time Complexity Analysis of the Simple Genetic Algorithm
Theoretical Computer Science, 605, pp. 21-41
DOI: https://dx.doi.org/10.1016/j.tcs.2015.01.002
Andrei Lissovoi and Carsten Witt (2015):
Runtime Analysis of Ant Colony Optimization on Dynamic Shortest Path Problems
Theoretical Computer Science, 561, pp. 73-85
DOI: https://dx.doi.org/10.1016/j.tcs.2014.06.035
Pietro S. Oliveto and Carsten Witt (2014):
On the Runtime Analysis of the Simple Genetic Algorithm
Theoretical Computer Science, 545, pp. 2-19
DOI: https://dx.doi.org/10.1016/j.tcs.2013.06.015
Carsten Witt (2014):
Fitness Levels with Tail Bounds for the Analysis of Randomized Search Heuristics
Information Processing Letters, 114(1-2), pp. 38-41
DOI: https://dx.doi.org/10.1016/j.ipl.2013.09.013
Carsten Witt (2013):
Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
Combinatorics, Probability and Computing, 22(2), pp. 294-318
DOI: https://dx.doi.org/10.1017/S0963548312000600
Per Kristian Lehre and Carsten Witt (2012):
Black-box Search by Unbiased Variation
Algorithmica, 64(4), pp. 623-642
DOI: https://dx.doi.org/10.1007/s00453-012-9616-8
Timo Kötzing, Frank Neumann, Heiko Röglin and Carsten Witt (2012):
Theoretical Analysis of Two ACO Approaches for the Traveling Salesman Problem
Swarm Intelligence, 6(1), pp. 1-21
DOI: https://dx.doi.org/10.1007/s11721-011-0059-7
Carsten Witt (2012):
Analysis of an Iterated Local Search Algorithm for Vertex Cover in Sparse Random Graphs
Theoretical Computer Science, 425(1), pp. 417-425
DOI: https://dx.doi.org/10.1016/j.tcs.2011.01.010
Benjamin Doerr, Frank Neumann, Dirk Sudholt and Carsten Witt (2011):
Runtime Analysis of the 1-ANT Ant Colony Optimizer
Theoretical Computer Science, 412(17), pp. 1629-1644
DOI: https://dx.doi.org/10.1016/j.tcs.2010.12.030
Pietro S. Oliveto and Carsten Witt (2011):
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Algorithmica, 59(3), pp. 369-386
DOI: https://dx.doi.org/10.1007/s00453-010-9387-z
Erratum: https://arxiv.org/abs/1211.7184
Frank Neumann and Carsten Witt (2010):
Ant Colony Optimization and the Minimum Spanning Tree Problem
Theoretical Computer Science, 411(25), pp. 2406-2413
DOI: https://dx.doi.org/10.1016/j.tcs.2010.02.012
Dirk Sudholt and Carsten Witt (2010):
Runtime Analysis of a Binary Particle Swarm Optimizer
Theoretical Computer Science, 411(21), pp. 2084-2100
DOI: https://dx.doi.org/10.1016/j.tcs.2010.03.002
Tobias Friedrich, Jun He, Niels Hebbinghaus, Frank Neumann and Carsten Witt (2010):
Approximating covering problems by randomized search heuristics using multi-objective models
Evolutionary Computation, 18(4), pp. 617-633
DOI: https://dx.doi.org/10.1162/EVCO_a_00003
Tobias Friedrich, Pietro S. Oliveto, Dirk Sudholt, and Carsten Witt (2009):
Analysis of Diversity-Preserving Mechanisms for Global Exploration
Evolutionary Computation, 17(4), pp. 455-476
DOI: https://dx.doi.org/10.1162/evco.2009.17.4.17401
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann and Carsten Witt (2009):
Analyses of Simple Hybrid Evolutionary Algorithms for the Vertex Cover Problem
Evolutionary Computation, 17(1), pp. 3-20
DOI: https://dx.doi.org/10.1162/evco.2009.17.1.3
Frank Neumann and Carsten Witt (2009):
Runtime Analysis of a Simple Ant Colony Optimization Algorithm
Algorithmica, 54(2), pp. 243-255
DOI: https://dx.doi.org/10.1007/s00453-007-9134-2
Frank Neumann, Dirk Sudholt and Carsten Witt (2009):
Analysis of Different MMAS ACO Algorithms on Unimodal Functions and Plateaus
Swarm Intelligence, 3(1), pp. 35-68
DOI: https://dx.doi.org/10.1007/s11721-008-0023-3
Carsten Witt (2008):
Population Size versus Runtime of a Simple Evolutionary Algorithm
Theoretical Computer Science, 403(1), pp. 104-120
DOI https://dx.doi.org/10.1016/j.tcs.2008.05.011
Jun He, Colin Reeves, Carsten Witt and Xin Yao (2007):
A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Existence and Predictability
Evolutionary Computation, 15(4), pp. 435-444
DOI: https://dx.doi.org/10.1162/evco.2007.15.4.435
Jörn Mehnen, Thomas Michelitsch and Carsten Witt (2007):
Collaborative Research Centre 531: Computational Intelligence - Theory and Practice
it - Information Technology, 49(1), Oldenbourg, pp. 49-57
DOI: https://dx.doi.org/10.1524/itit.2007.49.1.49
Carsten Witt (2006):
Runtime Analysis of the (μ+1) EA on Simple Pseudo-Boolean Functions
Evolutionary Computation, 14(1), pp. 65-86
DOI: https://dx.doi.org/10.1162/evco.2006.14.1.65
Ingo Wegener and Carsten Witt (2005):
On the Analysis of a Simple Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions
Journal of Discrete Algorithms, 3(1), pp. 61-78
DOI: https://dx.doi.org/10.1016/j.jda.2004.02.001
Ingo Wegener and Carsten Witt (2005):
On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
Combinatorics, Probability & Computing, 14, pp. 225-247
DOI: https://dx.doi.org/10.1017/S0963548304006650

Conference Publications

Martin S. Krejca, Frank Neumann and Carsten Witt (2025):
Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal
In: Proc. of Foundations of Genetic Algorithms - FOGA 2025, ACM Press, pp. 142-153
DOI: https://doi.org/10.1145/3729878.3746614
Sumit Adak and Carsten Witt (2025):
Runtime Analysis of a Compact Genetic Algorithm with High Selection Pressure
In: Proc. of Foundations of Genetic Algorithms - FOGA 2025, ACM Press, pp. 14-24
DOI: https://doi.org/10.1145/3729878.3746630
Sumit Adak and Carsten Witt (2025):
Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2025, ACM Press, pp. 585-1593
DOI: https://doi.org/10.1145/3712256.3726353
Sumit Adak and Carsten Witt (2025):
A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes
In: Proc. of European Conference on Evolutionary Computation in Combinatorial Optimisation - EvoCOP 2025, Springer, pp. 1-17
DOI: https://doi.org/10.1007/978-3-031-86849-8_1
Sumit Adak and Carsten Witt (2024):
Runtime Analysis of a Multi-valued Compact Genetic Algorithm on Generalized OneMax
In: Proc. of Parallel Problem Solving from Nature - PPSN 2024 (part III), Springer, pp. 53-69
DOI: https://doi.org/10.1007/978-3-031-70071-2_4
Frank Neumann and Carsten Witt (2024):
Sliding Window 3-Objective Pareto Optimization for Problems with Chance Constraints
In: Proc. of Parallel Problem Solving from Nature - PPSN 2024 (part III), Springer, pp. 36-52
DOI: https://doi.org/10.1007/978-3-031-70071-2_3
Paul Fischer, John Alasdair Warwicker and Carsten Witt (2024):
A Runtime Analysis of Bias-invariant Neuroevolution and Dynamic Fitness Evaluation
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2024, ACM Press, pp. 1560-1568
DOI: https://doi.acm.org?doi=3638529.3654044
Martin S. Krejca and Carsten Witt (2024):
A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2024, ACM Press, pp. 1578-1586
DOI: https://doi.acm.org?doi=3638529.3654076
Frank Neumann and Carsten Witt (2023):
Fast Pareto Optimization Using Sliding Window Selection
In: Proc. of European Conference on Artificial Intelligence - ECAI 2023, IOS Press, pp. 1171-1178
DOI: https://doi.org/10.3233/FAIA230463
Paul Fischer, Emil Lundt Larsen and Carsten Witt (2023):
First Steps Towards a Runtime Analysis of Neuroevolution
In: Proc. of Foundations of Genetic Algorithms - FOGA 2023, ACM Press, pp. 61-72
DOI: https://doi.org/10.1145/3594805.3607125
Best Paper Award
Frank Neumann and Carsten Witt (2023):
3-Objective Pareto Optimization for Problems with Chance Constraints
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2023, ACM Press, pp. 731-739
DOI: https://doi.org/10.1145/3583131.3590392
Benjamin Doerr, Taha El Ghazi El Houssaini, Amirhossein Rajabi and Carsten Witt (2023):
How Well Does the Metropolis Algorithm Cope With Local Optima?
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2023, ACM Press, pp. 1000-1008
DOI: https://doi.org/10.1145/3583131.3590390
Frank Neumann and Carsten Witt (2022):
Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
In: Proc. of International Joint Conferences on Artificial Intelligence - IJCAI 2022, pp. 4800-4806
DOI (Open Access): https://doi.org/10.24963/ijcai.2022/665
Frank Neumann and Carsten Witt (2022):
Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions
In: Proc. of Parallel Problem Solving from Nature - PPSN 2022 (part II), Springer, pp. 542-554
DOI: https://doi.org/10.1007/978-3-031-14721-0_38
Frank Neumann, Dirk Sudholt and Carsten Witt (2022):
The compact genetic algorithm struggles on Cliff functions
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2022, ACM Press, pp. 1426-1433
DOI: https://doi.org/10.1145/3512290.3528776
Benjamin Doerr, Amirhossein Rajabi and Carsten Witt (2022):
Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2022, ACM Press, pp. 1381-1389
DOI: https://doi.org/10.1145/3512290.3528812
Carsten Witt (2021):
On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution Algorithms
In: Proc. of Foundations of Genetic Algorithms - FOGA 2021, ACM Press, pp. 1-15
DOI: https://doi.org/10.1145/3450218.3477303
Amirhossein Rajabi and Carsten Witt (2021):
Stagnation detection in highly multimodal fitness landscapes
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2021, ACM Press, pp. 1178-1186
DOI: https://doi.org/10.1145/3449639.3459336
Amirhossein Rajabi and Carsten Witt (2021):
Stagnation Detection with Randomized Local Search
In: Proc. of European Conference on Evolutionary Computation in Combinatorial Optimisation - EvoCOP 2021, Springer, pp. 152-168
DOI: https://doi.org/10.1007/978-3-030-72904-2_10
Amirhossein Rajabi and Carsten Witt (2020):
Evolutionary Algorithms with Self-adjusting Asymmetric Mutation
In: Proc. of Parallel Problem Solving from Nature - PPSN 2020, Springer, pp. 664-677
DOI: https://doi.org/10.1007/978-3-030-58112-1_46
Timo Kötzing and Carsten Witt (2020):
Improved Fixed-Budget Results via Drift Analysis
In: Proc. of Parallel Problem Solving from Nature - PPSN 2020, Springer, pp. 648-660
DOI: https://doi.org/10.1007/978-3-030-58115-2_45
Amirhossein Rajabi and Carsten Witt (2020):
Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2020, ACM Press, pp. 1314-1322
DOI: https://doi.org/10.1145/3377930.3389833
Pietro S. Oliveto, Dirk Sudholt and Carsten Witt (2020):
A Tight Lower Bound on the Expected Runtime of Standard Steady State Genetic Algorithms
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2020, ACM Press, pp. 1323-1331
DOI: https://doi.org/10.1145/3377930.3390212
Hsien-Kuei Hwang and Carsten Witt (2019):
Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools
In: Proc. of Foundations of Genetic Algorithms XV - FOGA 2019, ACM Press, pp. 1-12
DOI: https://doi.org/10.1145/3299904.3340302
Andrew M. Sutton and Carsten Witt (2019):
Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2019, ACM Press, pp. 1515-1522
DOI: https://doi.org/10.1145/3321707.3321848
Frank Neumann, Mojgan Pourhassan and Carsten Witt (2019):
Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2019, ACM Press, pp. 1506-1514
DOI: https://doi.org/10.1145/3321707.3321722
Johannes Lengler, Dirk Sudholt and Carsten Witt (2018):
Medium Step Sizes are Harmful for the Compact Genetic Algorithm
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2018, ACM Press, pp. 1499-1506
DOI: https://doi.acm.org/10.1145/3205455.3205576
Carsten Witt (2018):
Domino Convergence: Why One Should Hill-Climb on Linear Functions
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2018, ACM Press, pp. 1539-1546
DOI: https://doi.acm.org/10.1145/3205455.3205581
Benjamin Doerr, Carsten Witt and Jing Yang (2018):
Runtime Analysis for Self-adaptive Mutation Rates
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2018, ACM Press, pp. 1475-1482
DOI: https://doi.acm.org/10.1145/3205455.3205569
Benjamin Doerr, Christian Gießen, Carsten Witt and Jing Yang (2017):
The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2017, ACM Press, pp. 1351-1358
DOI: https://doi.acm.org/10.1145/3071178.3071279
Carsten Witt (2017):
Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2017, ACM Press, pp. 1415-1422
Technical report including full proofs: arXiv report 1704.00026
DOI: https://doi.acm.org/10.1145/3071178.3071216
Martin S. Krejca and Carsten Witt (2017):
Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax
In: Proc. of Foundations of Genetic Algorithms - FOGA 2017, ACM Press, pp. 65-80
DOI: https://dx.doi.org/10.1145/3040718.3040724
Preprint
Dirk Sudholt and Carsten Witt (2016):
Update Strength in EDAs and ACO: How to Avoid Genetic Drift
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2016, ACM Press, pp. 61-68
DOI: https://dx.doi.org/10.1145/2908812.2908867
Technical report including full proofs: arXiv report 1607.04063
Andrei Lissovoi and Carsten Witt (2016):
The Impact of Migration Topology on the Runtime of Island Models in Dynamic Optimization
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2016, ACM Press, pp. 1155-1162
DOI: https://dx.doi.org/10.1145/2908812.2908843
Christian Gießen and Carsten Witt (2016):
Optimal Mutation Rates for the (1+λ) EA on OneMax
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2016, ACM Press, pp. 1147-1154
DOI: https://dx.doi.org/10.1145/2908812.2908912
Frank Neumann and Carsten Witt (2015):
On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
In: Proc. of International Joint Conferences on Artificial Intelligence - IJCAI 2015, pp. 3742-3748
Andrei Lissovoi and Carsten Witt (2015):
On the Utility of Island Models in Dynamic Optimization
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2015, ACM Press, pp. 1447-1454
Christian Gießen and Carsten Witt (2015):
Population Size vs. Mutation Strength for the (1+λ) EA on OneMax
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2015, ACM Press, pp. 1439-1446
Timo Kötzing, Andrei Lissovoi and Carsten Witt (2015):
(1+1) EA on Generalized Dynamic OneMax
In: Proc. of Foundations of Genetic Algorithms - FOGA 2015, ACM Press, pp. 40-51
Per Kristian Lehre and Carsten Witt (2014):
Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
In: Proc. of 25th International Symposium on Algorithms and Computation - ISAAC 2014, LNCS 8889, Springer, pp. 686-697
Best Paper Award
Andrei Lissovoi and Carsten Witt (2014):
MMAS vs. Population-Based EA on a Family of Dynamic Fitness Functions
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2014, ACM Press, pp. 1399-1406
Carsten Witt (2014):
Revised Analysis of the (1+1) EA for the Minimum Spanning Tree Problem
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2014, ACM Press, pp. 509-516
Best Paper Award
Benjamin Doerr, Thomas Jansen, Carsten Witt and Christine Zarges (2013):
A Method to Derive Fixed Budget Results from Expected Optimisation Times
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2013, ACM Press, pp. 1581-1588
Andrei Lissovoi and Carsten Witt (2013):
Runtime Analysis of Ant Colony Optimization on Dynamic Shortest Path Problems
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2013, ACM Press, pp. 1605-1612
Pietro Simone Oliveto and Carsten Witt (2013):
Improved Runtime Analysis of the Simple Genetic Algorithm
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2013, ACM Press, pp. 1621-1628
Benjamin Doerr, Paul Fischer, Astrid Hilbert and Carsten Witt (2013):
Evolutionary Algorithms for the Detection of Structural Breaks in Time Series (Extended Abstract)
In: Companion to GECCO 2013, ACM Press, pp. 119-120
Benjamin Doerr, Dirk Sudholt and Carsten Witt (2013):
When Do Evolutionary Algorithms Optimize Separable Functions in Parallel?
In: Proc. of Foundations of Genetic Algorithms - FOGA 2013, ACM Press, pp. 51-63
Pietro S. Oliveto and Carsten Witt (2012):
On the Analysis of the Simple Genetic Algorithm
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2012, ACM Press, pp. 1341-1348
Carsten Witt (2012):
Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation
In: Proc. of STACS 2012, LIPIcs, pp. 420-431
Proceedings version: https://drops.dagstuhl.de/opus/volltexte/2012/3392/
Technical report: https://arxiv.org/abs/1108.4386
Martin Ebbesen, Paul Fischer and Carsten Witt (2011):
Edge-matching Problems with Rotations
In: Proc. of Fundamentals of Computation Theory - FCT 2011, LNCS 6914, Springer, pp. 114-125
Technical report including full proofs: arXiv report 1703.09421
Benjamin Doerr, Mahmoud Fouz and Carsten Witt (2011):
Sharp Bounds by Probability-Generating Functions and Variable Drift
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2011, ACM Press, pp. 2083-2090
ACM Authorizer Link
Timo Kötzing, Frank Neumann, Heiko Röglin and Carsten Witt (2010):
Theoretical Properties of two ACO Approaches for the Traveling Salesman Problem
In: Proc. of Ant Colony Optimization and Swarm Intelligence - ANTS 2010, LNCS 6234, Springer, pp. 324-335
Best Paper Award
Frank Neumann, Dirk Sudholt, Carsten Witt (2010):
A few ants are enough: ACO with iteration-best update
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2010, ACM Press, pp. 63-70
Per Kristian Lehre and Carsten Witt (2010):
Black-box search by unbiased variation
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2010, ACM Press, pp. 1441-1448
Best Paper Award
Benjamin Doerr, Mahmoud Fouz and Carsten Witt (2010):
Quasirandom evolutionary algorithms
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2010, ACM Press, pp. 1457-1464
Frank Neumann, Pietro Oliveto and Carsten Witt (2009):
Theoretical Analysis of Fitness-proportional Selection: Landscapes and Efficiency
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2009, ACM Press, pp. 835-842
Carsten Witt (2009):
Greedy Local Search and Vertex Cover in Sparse Random Graphs
In: Proc. of the 6th Annual Conference on Theory and Applications of Models of Computation - TAMC 2009, LNCS 5532, Springer, pp. 410-419
Carsten Witt (2009):
Why Standard Particle Swarm Optimizers Elude a Theoretical Runtime Analysis
In: Proc. of Foundations of Genetic Algorithms - FOGA 2009, ACM Press, pp. 13-20
Pietro S. Oliveto and Carsten Witt (2008):
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
In: Proc. of Parallel Problem Solving from Nature - PPSN X, LNCS 5199, Springer, pp. 82-91
Preliminary Version: Technical Report, Reihe CI, No. CI-247/08, SFB 531, Technische Universität Dortmund, Germany
Download: CI Report 247/08 (PDF)
Frank Neumann, Dirk Sudholt and Carsten Witt (2008):
Rigorous Analyses for the Combination of Ant Colony Optimization and Local Search
In: Proc. of Ant Colony Optimization and Swarm Intelligence - ANTS 2008, LNCS 5217, Springer, pp. 132-143
Preliminary Version: Technical Report, Reihe CI, No. CI-243/08, SFB 531, Technische Universität Dortmund, Germany
Download: CI Report 243/08 (PDF)
Dirk Sudholt and Carsten Witt (2008):
Runtime Analysis of Binary PSO
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2008, ACM Press, pp. 135-142
Preliminary Version: Technical Report, Reihe CI, No. CI-241/08, SFB 531, Technische Universität Dortmund, Germany
Download: CI Report 241/08 (PDF)
Tobias Friedrich, Pietro Oliveto, Dirk Sudholt and Carsten Witt (2008):
Theoretical Analysis of Diversity Mechanisms for Global Exploration
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2008, ACM Press, pp. 945-952
Best Paper Award
Preliminary Version: Technical Report, Reihe CI, No. CI-237/08, SFB 531, Technische Universität Dortmund, Germany
Download: CI Report 237/08 (PDF)
Frank Neumann and Carsten Witt (2008):
Ant Colony Optimization and the Minimum Spanning Tree Problem
In: Proc. of Learning and Intelligent Optimization - LION 2, LNCS 5313, Springer, pp. 153-166
Preliminary version: Electronic Colloquium on Computational Complexity (ECCC), Report No. 143.
Download: ECCC Report TR06-143
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann and Carsten Witt (2007):
On Improving Approximate Solutions by Evolutionary Algorithms
In: Proc. of the Congress on Evolutionary Computation - CEC 2007, IEEE Press, pp. 2614-2621
Frank Neumann, Dirk Sudholt and Carsten Witt (2007):
Comparing Variants of MMAS ACO Algorithms on Pseudo-Boolean Functions
In: Proc. of Engineering Stochastic Local Search Algorithms - SLS 2007, LNCS 4638, Springer, pp. 61-75
Preliminary Version: Technical Report, Reihe CI, No. CI-230/07, SFB 531, Universität Dortmund, Germany
Download: CI Report 230/07 (PDF)
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann and Carsten Witt (2007):
Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2007, ACM Press, pp. 797-804
Preliminary Version: Technical Report, Reihe CI, No. CI-224/07, SFB 531, Universität Dortmund, Germany
Download: CI Report 224/07 (PDF)
Benjamin Doerr, Frank Neumann, Dirk Sudholt and Carsten Witt (2007):
On the Runtime Analysis of the 1-ANT ACO Algorithm
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2007, ACM Press, pp. 33-40
Best Paper Award
Preliminary Version: Technical Report, Reihe CI, No. CI-223/07, SFB 531, Universität Dortmund, Germany
Download: CI Report 223/07 (PDF)
Frank Neumann and Carsten Witt (2006):
Runtime Analysis of a Simple Ant Colony Optimization Algorithm (Extended Abstract)
In: Proc. of ISAAC 2006, LNCS 4288, pp. 618-627, Springer
See also: Electronic Colloquium on Computational Complexity (ECCC), Report No. 84.
Download: ECCC Report TR06-084
Jens Jägersküpper and Carsten Witt (2005):
Rigorous Runtime Analysis of a (μ+1) ES for the Sphere Function
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2005, ACM press, pp. 849-856
Download: Authors' version (PDF) © ACM, 2005. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in https://doi.acm.org/10.1145/1068009.1068153.
Carsten Witt (2005):
Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics
In: Proc. of the 22nd Annual Symposium on Theoretical Aspects of Computer Science - STACS 2005, LNCS 3404, Springer, pp. 44-56
Download: Revised preprint (PDF)
Carsten Witt (2004):
An Analysis of the (μ+1) EA on Simple Pseudo-Boolean Functions
In: Genetic and Evolutionary Computation Conference - GECCO 2004, LNCS 3102, Springer, pp. 761-773
Best paper award
Download: Preprint (PDF)
Ingo Wegener and Carsten Witt (2003):
On the Optimization of Monotone Polynomials by the (1+1) EA and Randomized Local Search.
In: Proc. of Genetic and Evolutionary Computation Conference - GECCO 2003, LNCS 2723, Springer, pp. 622-633
Best paper award
Download: Preprint (PDF)
Carsten Witt (2003):
Population Size vs. Runtime of a Simple EA
Proc. of the Congress on Evolutionary Computation - CEC 2003, volume 3, IEEE Press, pp. 1996-2003
Susanne Albers and Carsten Witt (2001):
Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows
In: Proc. of Approximation, Randomization and Combinatorial Optimization - APPROX 2001, LNCS 2129, Springer, pp. 12-23
Download: Authors' version (PDF) © Springer

Theses

Carsten Witt (2004):
Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung
PhD Thesis, University of Dortmund
Available online (in German): Download PDF version
Carsten Witt (2000):
Die Analyse des (1+1)-EA für fast lineare und spezielle quadratische Funktionen
Diploma Thesis, University of Dortmund
Available online (in German): Postscript (953K) / gzipped Postscript (340K) / PDF (753K) / gzipped PDF (631K)

Carsten Witt

Professor

Publications

Books

Book Chapters

Editorial Work

Journal Articles

Conference Publications

Theses

Teaching