Dr. Dirk Sudholt

I am a Lecturer at the University of Sheffield in the Department of Computer Science. Before coming to Sheffield, I obtained my Diplom and my Ph.D. from the Technische Universität Dortmund under the supervision of Prof. Ingo Wegener. I have held postdoc positions at the International Computer Science Institute (ICSI) in Berkeley, California, in the group of Prof. Richard M. Karp as well as the University of Birmingham, working with Prof. Xin Yao in the SEBASE project. I am interested in randomized algorithms, algorithmic analysis, and combinatorial optimization. My main expertise is the analysis of randomized search heuristics such as evolutionary algorithms, hybridizations with local search, and ant colony optimization. Contact Information Address: Department of Computer Science The University of Sheffield Regent Court, 211 Portobello Sheffield S1 4DP United Kingdom E-mail: d.sudholtsheffield.ac.uk Phone: +44 114 222 1848

Recent Activities

• I am looking for a highly motivated PhD student interested in runtime analysis of bio-inspired computation at the University of Sheffield.
• I have been elected to the Editorial Board of Evolutionary Computation.
• Our paper Timo Kötzing, Dirk Sudholt, and Madeleine Theile (2011): How Crossover Helps in Pseudo-Boolean Optimization has won the best paper award in the GECCO 2011 track 'Genetic Algorithms'.
• I gave a tutorial called Theory of Swarm Intelligence at GECCO 2011.
  Download slides
• I was one of two invited tutorial speakers at ThRaSH 2011.
  Download slides

Publications

Book Chapters

• Dirk Sudholt (2012): Parallel Evolutionary Algorithms.
  To appear in Janusz Kacprzyk and Witold Pedrycz (Eds.): Handbook of Computational Intelligence, Springer.
  
• Dirk Sudholt (2012): Parametrization and Balancing Global and Local Search.
  In F. Neri, C. Cotta, and P. Moscato (Eds.): Handbook of Memetic Algorithms, Studies in Computational Intelligence, Vol. 379, ISBN 978-3-642-23246-6, Springer.
  Download preprint
• Dirk Sudholt (2011): Memetic Evolutionary Algorithms.
  In A. Auger, B. Doerr (Eds.): Theory of Randomized Search Heuristics - Foundations and Recent Developments, Series on Theoretical Computer Science 1, ISBN: 978-981-4282-66-6, World Scientific.
  
• Frank Neumann, Dirk Sudholt, and Carsten Witt (2009): Computational Complexity of Ant Colony Optimization and its Hybridization with Local Search.
  L.C. Jain, S. Dehuri, CP Lim (Eds.): Innovations in Swarm Intelligence, SGI 248, ISBN: 978-3-642-04224-9, Springer.
  Download preliminary version

Journal Articles

• Benjamin Doerr and Thomas Jansen and Dirk Sudholt and Carola Winzen and Christine Zarges (2012):
  Mutation Rate Matters Even When Optimizing Monotone Functions.
  To appear in Evolutionary Computation.
  
• Dirk Sudholt and Christian Thyssen (2012):
  A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems.
  To appear in Algorithmica.
  Download preprint
• Dirk Sudholt and Christian Thyssen (2012):
  Running Time Analysis of Ant Colony Optimization for Shortest Path Problems.
  Journal of Discrete Algorithms, Volume 10, January 2012, pages 165-180.
  Download preprint
• Benjamin Doerr, Frank Neumann, Dirk Sudholt, and Carsten Witt (2011):
  Runtime analysis of the 1-ANT ant colony optimizer.
  Theoretical Computer Science, 412(17), 1629-1644.
  
• Dirk Sudholt (2011):
  Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima.
  Algorithmica, 59(3), 343-368.
  
• Dirk Sudholt and Carsten Witt (2010):
  Runtime Analysis of a Binary Particle Swarm Optimizer.
  Theoretical Computer Science, 411(21), 2084-2100.
  
• Thomas Sauerwald and Dirk Sudholt (2010):
  A Self-stabilizing Algorithm for Cut Problems in Synchronous Networks.
  Theoretical Computer Science, 411(14-15), 1599-1612.
  
• Thomas Jansen and Dirk Sudholt (2010):
  Analysis of an Asymmetric Mutation Operator.
  Evolutionary Computation, 18(1), 1-26.
  
• Tobias Friedrich, Pietro S. Oliveto, Dirk Sudholt, and Carsten Witt (2009):
  Analysis of Diversity-Preserving Mechanisms for Global Exploration.
  Evolutionary Computation, 17(4), 455-476.
  
• Dirk Sudholt (2009):
  The Impact of Parametrization in Memetic Evolutionary Algorithms.
  Theoretical Computer Science, 410(26), 2511-2528.
  
• Frank Neumann, Dirk Sudholt, and Carsten Witt (2009):
  Analysis of different MMAS ACO algorithms on unimodal functions and plateaus.
  Swarm Intelligence, 3(1), 35-68.
  

Conference Articles

• Alberto Moraglio and Dirk Sudholt (2012):
  Runtime Analysis of Convex Evolutionary Search
  To appear in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012). ACM press.
  
• Leandro L. Minku, Dirk Sudholt, and Xin Yao (2012):
  Evolutionary Algorithms for the Project Scheduling Problem: Runtime Analysis and Improved Design
  To appear in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012). ACM press.
  
• Dirk Sudholt (2012):
  Crossover Speeds Up Building-Block Assembly
  To appear in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012). ACM press.
  
• Jonathan E. Rowe and Dirk Sudholt (2012):
  The Choice of the Offspring Population Size in the (1,λ) EA
  To appear in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012). ACM press.
  
• Jörg Lässig and Dirk Sudholt (2011):
  Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization
  Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011). LNCS 7074, Springer, pages 405-414.
  Download preliminary version
• Timo Kötzing, Dirk Sudholt, and Madeleine Theile (2011):
  How Crossover Helps in Pseudo-Boolean Optimization
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011). ACM Press, pages 989-996.
  Best paper award in the track 'Genetic Algorithms'.
• Frank Neumann, Pietro S. Oliveto, Günter Rudolph, and Dirk Sudholt (2011):
  On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011). ACM press, pages 1587-1594.
  
• Timo Kötzing, Frank Neumann, Dirk Sudholt, and Markus Wagner (2011):
  Simple Max-Min Ant Systems and the Optimization of Linear Pseudo-Boolean Functions
  Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011). ACM Press, pages 209-218.
  Download preliminary version
• Jörg Lässig and Dirk Sudholt (2011):
  Adaptive Population Models for Offspring Populations and Parallel Evolutionary Algorithms
  Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011). ACM Press, pages 181-192.
  Download preliminary version
• Dirk Sudholt (2011):
  Using Markov-Chain Mixing Time Estimates for the Analysis of Ant Colony Optimization
  Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011). ACM Press, pages 139-150.
  
• Dirk Sudholt and Christine Zarges (2010):
  Analysis of an Iterated Local Search Algorithm for Vertex Coloring
  Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010). LNCS 6506, Springer, pages 340-352.
  
• Jörg Lässig and Dirk Sudholt (2010):
  Experimental Supplements to the Theoretical Analysis of Migration in the Island Model
  Parallel Problem Solving from Nature (PPSN 2010). LNCS 6238, Springer, pages 224-233.
  
• Benjamin Doerr and Thomas Jansen and Dirk Sudholt and Carola Winzen and Christine Zarges (2010):
  Optimizing Monotone Functions Can Be Difficult
  Parallel Problem Solving from Nature (PPSN 2010). LNCS 6238, Springer, pages 42-51.
  
• Jörg Lässig and Dirk Sudholt (2010):
  General Scheme for Analyzing Running Times of Parallel Evolutionary Algorithms
  Parallel Problem Solving from Nature (PPSN 2010). LNCS 6238, Springer, pages 234-243.
  Best paper award.
  
• Dirk Sudholt (2010):
  General Lower Bounds for the Running Time of Evolutionary Algorithms
  Parallel Problem Solving from Nature (PPSN 2010). LNCS 6238, Springer, pages 124-133.
  Download full conference version, download extended journal version
• Jörg Lässig and Dirk Sudholt (2010):
  The Benefit of Migration in Parallel Evolutionary Algorithms.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010). ACM Press, pages 1105-1112.
  Best paper award in the track 'Parallel Evolutionary Systems'.
  
• Christian Horoba and Dirk Sudholt (2010):
  Ant Colony Optimization for Stochastic Shortest Path Problems.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010). ACM Press, pages 1465-1472.
  Nominated for a best paper award in the track 'Theory'.
  
• Frank Neumann, Dirk Sudholt and Carsten Witt (2010):
  A Few Ants are Enough: ACO with Iteration-Best Update.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010). ACM Press, pages 63-70.
  Nominated for a best paper award in the track 'ACO/Swarm Intelligence'.
  
• Christian Horoba and Dirk Sudholt (2009):
  Running Time Analysis of ACO Systems for Shortest Path Problems
  Engineering Stochastic Local Search Algorithms (SLS 2009). LNCS 5752, Springer, pages 76-91.
  Download preprint
• Frank Neumann, Dirk Sudholt, and Carsten Witt (2008):
  Rigorous Analyses for the Combination of Ant Colony Optimization and Local Search.
  Proceedings of the Sixth International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS 2008). LNCS 5217, Springer, pages 132-143.
  Download technical report
• Thomas Sauerwald and Dirk Sudholt (2008):
  Self-stabilizing Cuts in Synchronous Networks.
  Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008). LNCS 5058, Springer, pages 234-246.
  Download technical report
• Dirk Sudholt and Carsten Witt (2008):
  Runtime Analysis of Binary PSO.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). ACM Press, pages 135-142.
  Download technical report
• Dirk Sudholt (2008):
  Memetic Algorithms with Variable-Depth Search to Overcome Local Optima.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). ACM Press, pages 787-794.
  Nominated for a best paper award in the track 'Formal Theory'.
  Download technical report
• Tobias Friedrich, Pietro Oliveto, Dirk Sudholt, and Carsten Witt (2008):
  Theoretical Analysis of Diversity Mechanisms for Global Exploration.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). ACM Press, pages 945-952.
  Best paper award in the track 'Genetic Algorithms'.
  Download technical report
• Frank Neumann, Dirk Sudholt, and Carsten Witt (2007):
  Comparing Variants of MMAS ACO Algorithms on Pseudo-Boolean Functions.
  Engineering Stochastic Local Search Algorithms (SLS 2007). LNCS 4638, Springer, pages 61-75.
  Download technical report
• Benjamin Doerr, Frank Neumann, Dirk Sudholt, and Carsten Witt (2007):
  On the Runtime Analysis of the 1-ANT ACO Algorithm.
  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007). ACM Press, pages 33-40.
  Best paper award in the track 'Ant Colony Optimization, Swarm Intelligence, and Artificial Immune Systems'.
  Download technical report
• Dirk Sudholt (2006):
  Local Search in Evolutionary Algorithms: the Impact of the Local Search Frequency.
  In Tetsuo Asano (Ed.): Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006). LNCS 4288, Springer, pages 359-368.
  Download more detailed technical report
• Dirk Sudholt (2006):
  On the Analysis of the (1+1) Memetic Algorithm.
  In Maarten Keijzer et al. (Eds.): Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006). ACM Press, pages 493-500.
  Download technical report
• Thomas Jansen and Dirk Sudholt (2005):
  Design and Analysis of an Asymmetric Mutation Operator.
  Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2005). IEEE Press, pages 497-504.
  Download revised technical report
• Dirk Sudholt (2005):
  Crossover is Provably Essential for the Ising Model on Trees.
  In H.-G. Beyer et al. (Eds.): Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005). ACM Press, pages 1161-1167.
  Download technical report
• Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener (2004):
  Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization.
  In Xin Yao et al. (Eds.): Proceedings of the 8th International Conference on Parallel Problem Solving From Nature (PPSN VIII). LNCS 3242, Springer, pages 21-30.
  Download technical report
• Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener (2004):
  The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes.
  In Xin Yao et al. (Eds.): Proceedings of the 8th International Conference on Parallel Problem Solving From Nature (PPSN VIII). LNCS 3242, Springer, pages 31-40.
  Download technical report

Theses

• Dirk Sudholt (2008):
  Computational Complexity of Evolutionary Algorithms, Hybridizations, and Swarm Intelligence
  Dissertation, Technische Universität Dortmund

  Download PDF version

• Dirk Sudholt (2004):
  Evolutionäre Algorithmen als Adaptationsschemata (Evolutionary Algorithms as Adaptation Schemes)
  Diploma Thesis, Universität Dortmund

  Available online (in German):  Postscript (1.2 MB) /  zipped Postscript (398.5 KB) /  PDF (1.1 MB)