Carsten Witt

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

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: http://www.springer.com/978-3-642-16543-6
  DOI: http://dx.doi.org/10.1007/978-3-642-16544-3

Book Chapters

• Carsten Witt (2011):
  Theory of Particle Swarm Optimization
  In A. Auger and B. Doerr (Eds.): Theory of Randomized Search Heuristics, World Scientific Publishing

• 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: http://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: http://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

Journal Articles

• Per Kristian Lehre and Carsten Witt (2012):
  Black-box Search by Unbiased Variation
  Algorithmica, to appear

• 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, 12(1), pp. 1-21
  DOI: 10.1007/s11721-011-0059-7

• Carsten Witt (2011):
  Analysis of an Iterated Local Search Algorithm for Vertex Cover in Sparse Random Graphs
  Theoretical Computer Science, to appear
  DOI: http://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: http://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: http://dx.doi.org/10.1007/s00453-010-9387-z

• Frank Neumann and Carsten Witt (2010):
  Ant Colony Optimization and the Minimum Spanning Tree Problem
  Theoretical Computer Science, 411(25), pp. 2406-2413
  DOI: http://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: http://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: http://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: http://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: http://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: http://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: http://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 http://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: http://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: http://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: http://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: http://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: http://dx.doi.org/10.1017/S0963548304006650

Conference Publications

• Carsten Witt (2012):
  Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation
  In: Proc. of STACS 2012, to appear
  Technical report: http://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

• Per Kristian Lehre and Carsten Witt (2011):
  Finite First Hitting Time versus Stochastic Convergence in Particle Swarm Optimisation
  In: Proc. of MIC 2011, to appear
  Extended technical report: http://arxiv.org/abs/1105.5540

• Benjamin Doerr, Mahmoud Fouz and Carsten Witt (2011):
  Sharp Bounds by Probability-Generating Functions and Variable Drift
  In: Proc. of Genetic and Evolutionary Computation - GECCO 2011, ACM Press, pp. 2083-2090

• 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 - 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 - 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 - 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 - 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, pp. 13-20, ACM Press
  

• 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, pp. 82-91, Springer
  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, pp. 132-143, Springer
  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 http://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)

Teaching

• Computationally Hard Problems, Fall 2011
• Algorithms for Massive Data Sets, Spring 2011
• CDIO project, Spring 2011
• Computationally Hard Problems, Fall 2010
• Algorithms for Massive Data Sets, Spring 2010
• Computationally Hard Problems, Fall 2009
• Artificial Intelligence and Multi-agent Systems, Spring 2009
• Lectures "KT 2008/09"
• Lectures "CI 2007/08"
• Tutorials "EA 2007"
• Tutorials "EA 2002"
• Tutorials "GTI 2001"