max planck institut
informatik

Benjamin Doerr: Publications

[Copyright notice: Below you can find preprints of my work to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders. It is your responsibility to respect these rights. Some publishers want me to put up this notice. Personally, I like you reading my papers.]

---

Editorial Work

---

• A. Auger, B. Doerr (Eds.).
  Theory of Randomized Search Heuristics. [link]
  World Scientific Publishing, 2011. 360 pages.
  
  
• Guest Editors: B. Doerr, T. Jansen.
  Algorithmica 59, Number 3. Theory of Evolutionary Computation.
  Springer Verlag, 2011.
  
  
• Guest Editors: B. Doerr, F. Neumann, I. Wegener.
  Algorithmica 57, Number 1. Including a Special Section on Genetic and Evolutionary Computation.
  Springer Verlag, 2010. 119-206.
  
  
• G.R. Raidl, E. Alba, J. Bacardit, H.-G. Beyer, M. Birattari, C. Blum, P.A.N. Bosman, C.B. Congdon, D. Corne, C. Cotta, M. Di Penta, B. Doerr, R. Drechsle, M. Ebner, J. Grahl, T. Jansen, J.D. Knowles, T. Lenaerts, M. Middendorf, J. F. Miller, M. O'Neill, R. Poli, G. Squillero, K.O. Stanley, T. Stützle, J. van Hemert (Eds.).
  GECCO 2009: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation.
  ACM Press, New York, 2009. 1956 pages.
  
  
• M. Keijzer, G. Antoniol, C. Bates Congdon, K. Deb, B. Doerr, N. Hansen, J. H. Holmes, G. S. Hornby, D. Howard, J. Kennedy, S. Kumar, F. G. Lobo, J. Francis Miller, J. Moore, F. Neumann, M. Pelikan, J. Pollack, K. Sastry, K. Stanley, A. Stoica, E. Talbi, I. Wegener (Eds.).
  GECCO 2008: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation.
  ACM Press, New York, 2008. 1786 pages.
  
  
• D. Thierens, H.-G. Beyer, J. Bongard, J. Branke, J. A. Clark, D. Cliff, C. B. Congdon, K. Deb, B. Doerr, T. Kovacs, S. Kumar, J. F. Miller, J. Moore, F. Neumann, M. Pelikan, R. Poli, K. Sastry, K. O. Stanley, T. Stützle, R. A. Watson, I. Wegener (Eds.).
  GECCO 2007: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation.
  ACM Press, New York, 2007. 2269 pages.
  
  

---

Journal Papers

---

• B. Doerr, D. Johannsen, C. Winzen.
  Multiplicative drift analysis. [pdf (arxiv)]
  Algorithmica, to appear.
  
  
• B. Doerr, M. Fouz, T. Friedrich.
  Why rumors spread fast in social networks.
  Communications of the ACM, to appear.
  
  
• B. Doerr, T. Jansen, D. Sudholt, C. Winzen, C. Zarges.
  Mutation rate matters even when optimizing monotone functions. [pdf (arxiv)]
  Evolutionary Computation, to appear.
  
  
• B. Doerr, L. A. Goldberg.
  Adaptive drift analysis. [pdf (arxiv)]
  Algorithmica, to appear.
  
  
• B. Doerr, D. Johannsen, C. Winzen.
  Non-existence of linear universal drift functions. [link]
  Theoretical Computer Science 436 (2012), 71-86.
  
  
• B. Doerr, E. Happ, C. Klein.
  Crossover can provably be useful in evolutionary computation. [pdf] [link]
  Theoretical Computer Science 425 (2012), 17-33.
  
  
• B. Doerr, C. Winzen.
  Memory-restricted black-box complexity of OneMax. [pdf] [link]
  Information Processing Letters 112 (2012), 32-34.
  
  
• B. Doerr, T. Friedrich, M. Künnemann, T. Sauerwald.
  Quasirandom rumor spreading: An experimental analysis. [pdf] [link]
  Journal of Experimental Algorithmics (JEA) 16 (2011), Article 3.3.
  
  
• B. Doerr, E. Happ, C. Klein.
  Tight analysis of the (1+1)-EA for the single source shortest path problem. [preprint pdf] [link]
  Evolutionary Computation 19 (2011), 673-691.
  
  
• B. Doerr, C. Winzen.
  Memory-Restricted Black-Box Complexity. [link]
  Electronic Colloquium on Computational Complexity (ECCC) 18, Research Paper 92 (2011).
  
  
• B. Doerr, A. Eremeev, F. Neumann, M. Theile, C. Thyssen.
  Evolutionary algorithms and dynamic programming. [link]
  Theoretical Computer Science 412 (2011), 6020-6035.
  
  
• B. Doerr, F. Neumann, D. Sudholt, C. Witt.
  Runtime analysis of the 1-ANT ant colony optimizer. [link]
  Theoretical Computer Science 412 (2011), 1629-1644.
  
  
• B. Doerr, M. Fouz.
  Quasi-random rumor spreading: Reducing randomness can be costly. [pdf (arxiv)] [link]
  Information Processing Letters 111 (2011), 277-230.
  
  
• B. Doerr, T. Jansen.
  Editorial. [link]
  Algorithmica 59 (2011), 299-300.
  
  
• J. Cooper, B. Doerr, T. Friedrich, J. Spencer.
  Deterministic random walks on regular trees. [pdf] [link]
  Random Structures & Algorithms 37 (2010), 353-366.
  
  
• B. Doerr, M. Fouz.
  Hereditary discrepancies in different numbers of colors II. [pdf (arxiv)] [link]
  SIAM Journal on Discrete Mathematics 24 (2010), 1205-1213.
  
  
• B. Doerr, F. Neumann.
  In memoriam: Ingo Wegener. [link]
  Algorithmica 58 (2010), 541-542.
  
  
• B. Doerr, F. Neumann, I. Wegener.
  Editorial. [link]
  Algorithmica 57 (2010), 119-120.
  
  
• B. Doerr, M. Gnewuch, M. Wahlström.
  Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. [link]
  Journal of Complexity 26 (2010), 490-507.
  
  
• S. Angelopoulos, B. Doerr, A. Huber, K. Panagiotou.
  Tight bounds for quasirandom rumor spreading. [pdf] [link]
  Electronic Journal of Combinatorics 16 (2009), Research Paper 102.
  
  
• B. Doerr, T. Friedrich.
  Deterministic random walks on the two-dimensional grid. [pdf] [link]
  Combinatorics, Probability & Computing 18 (2009), 123-144.
  
  
• B. Doerr, M. Gnewuch, P. Kritzer, F. Pillichshammer.
  Component-by-component construction of low-discrepancy point sets of small size. [link]
  Monte Carlo Methods and Applications 14 (2008), 129-149.
  
  
• J. Cooper, B. Doerr, J. Spencer, G. Tardos.
  Deterministic random walks on the integers. [pdf] [ps] [link]
  European Journal of Combinatorics 28 (2007), 2072-2090.
  
  
• B. Doerr, N. Hebbinghaus, F. Neumann.
  Speeding up evolutionary algorithms through unsymmetric mutation operators. [link]
  Evolutionary Computation 5 (2007), 401-410.
  
  
• B. Doerr.
  Matrix approximation and Tusnady's Problem. [pdf] [ps] [link]
  European Journal of Combinatorics 28 (2007), 990-995.
  
  
• N. Ahuja, A. Baltz, B. Doerr, A. Prívetivý, A. Srivastav.
  On the minimum load coloring problem. [pdf] [ps] [link]
  Journal of Discrete Algorithms 5 (2007), 533-545.
  
  
• B. Doerr.
  L_p linear discrepancy of totally unimodular matrices. [pdf] [ps] [link]
  Linear Algebra and Its Applications 420 (2007), 663-666.
  
  
• I. Bárány, B. Doerr.
  Balanced partitions of vector sequences. [pdf] [ps] [link]
  Linear Algebra and Applications 414 (2006), 464-469.
  
  
• B. Doerr.
  Matrix rounding with respect to small submatrices. [pdf] [ps] [link]
  Random Structures & Algorithms 28 (2006), 107-112.
  
  
• B. Doerr.
  Non-independent randomized rounding and coloring. [pdf] [ps] [link]
  Discrete Applied Mathematics 154 (2006), 650-659.
  
  
• B. Doerr, M. Gnewuch, N. Hebbinghaus.
  Discrepancy of symmetric products of hypergraphs. [pdf] [ps] [link]
  Electronic Journal of Combinatorics 13 (2006), Research Paper 40.
  
  
• B. Doerr, N. Hebbinghaus, S. Werth.
  Improved bounds and schemes for the declustering problem. [pdf] [ps] [link]
  Theoretical Computer Science 359 (2006), 123-132.
  
  
• B. Doerr, U. Lorenz.
  Error propagation in game trees. [pdf] [ps] [link]
  Mathematical Methods of Operations Research 64 (2006), 79-93.
  
  
• S. Teramoto, T. Asano, N. Katoh, B. Doerr.
  Inserting points uniformly at every instance. [pdf] [ps] [link]
  IEICE Transactions on Information and Systems E89-D (2006), 2348-2356.
  
  
• B. Doerr, M. Gnewuch, A. Srivastav.
  Bounds and constructions for the star-discrepancy via delta-covers. [pdf] [ps] [link]
  Journal of Complexity 21 (2005), 691-709.
  
  
• B. Doerr.
  The hereditary discrepancy is nearly independent of the number of colors. [pdf] [ps] [link]
  Proceedings of the American Mathematical Society 132 (2004), 1905-1912.
  
  
• B. Doerr.
  Linear discrepancy of totally unimodular matrices. [pdf] [ps] [link]
  Combinatorica 24 (2004), 117-125.
  
  
• B. Doerr.
  Global roundings of sequences. [pdf] [ps] [link]
  Information Processing Letters 92 (2004), 113-116.
  
  
• B. Doerr.
  Nonindependent randomized rounding and an application to digital halftoning. [pdf] [ps] [link]
  SIAM Journal on Computing 34 (2004), 299-317.
  
  
• B. Doerr.
  European tenure games. [pdf] [ps] [link]
  Theoretical Computer Science 313 (2004), 339-351.
  
  
• B. Doerr.
  Typical rounding problems. [pdf] [ps] [link]
  Theoretical Computer Science 312 (2004), 463-477.
  
  
• B. Doerr, A. Srivastav, P. Wehr.
  Discrepancy of cartesian products of arithmetic progressions. [pdf] [ps] [link]
  Electronic Journal of Combinatorics 11 (2004), Research Paper 5.
  
  
• B. Doerr, A. Srivastav.
  Multicolour discrepancies. [pdf] [ps] [link]
  Combinatorics, Probability & Computing 12 (2003), 365-399.
  
  
• N. Alon, B. Doerr, T. Luczak, T. Schoen.
  On the discrepancy of combinatorial rectangles. [pdf] [ps] [link]
  Random Structures & Algorithms 21 (2002), 205-215.
  
  
• B. Doerr.
  Discrepancy in different numbers of colors. [pdf] [ps] [link]
  Discrete Mathematics 250 (2002), 63-70.
  
  
• B. Doerr.
  Vector balancing games with aging. [pdf] [ps] [link]
  Journal of Combinatorial Theory, Series A 95 (2001), 219-233.
  
  
• G. Agnarsson, B. Doerr, T. Schoen.
  Coloring t-dimensional m-boxes. [pdf] [ps] [link]
  Discrete Mathematics 226 (2001), 21-33.
  
  
• B. Doerr.
  Linear discrepancy of basic totally unimodular matrices. [pdf] [ps] [link]
  Electronic Journal of Combinatorics 7 (2000), Research Paper 48.
  
  
• B. Doerr.
  Linear and hereditary discrepancy. [pdf] [ps] [link]
  Combinatorics, Probability & Computing 9 (2000), 349-354.
  
  

---

Conference Papers

---

• B. Doerr, M. Fouz, T. Friedrich.
  Asynchronous rumor spreading in preferential attachment graphs.
  In 13th Scandinavian Workshop on Algorithm Theory (SWAT 2012) , 2012, to appear.
  
  
• B. Doerr, C. Winzen.
  Reducing the arity in unbiased black-box complexity.
  In Genetic and Evolutionary Computation Conference (GECCO 2012), 2012, to appear.
  
  
• B. Doerr, T. Kötzing, A. R. Rota.
  Ants easily solve stochastic shortest path problems.
  In Genetic and Evolutionary Computation Conference (GECCO 2012), 2012, to appear.
  
  
• B. Doerr, S. Pohl.
  Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet.
  In Genetic and Evolutionary Computation Conference (GECCO 2012), 2012, to appear.
  
  
• B. Doerr, C. Winzen.
  Playing Mastermind with constant-size memory. [link]
  In Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS'12), pages 441-452, 2012. LIPIcs.
  
  
• T. Asano, B. Doerr.
  Memory-constrained algorithms for shortest path problem. [pdf]
  In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), pages 315-319, 2011.
  
  
• B. Doerr, M. Fouz, C. Witt.
  Sharp bounds by probability-generating functions and variable drifts. [link]
  In Genetic and Evolutionary Computation Conference (GECCO 2011), pages 2083-2090, 2011. ACM.
  
  
• B. Doerr, T. Kötzing, C. Winzen.
  Too fast unbiased black-box algorithms. [link]
  In Genetic and Evolutionary Computation Conference (GECCO 2011), pages 2043-2050, 2011. ACM.
  
  
• B. Doerr.
  Drift analysis. [link]
  In Genetic and Evolutionary Computation Conference (GECCO 2011), Companion Material, pages 1311-1320, 2011. ACM.
  
  
• B. Doerr, T. Kötzing, J. Lengler, C. Winzen.
  Black-box complexities of combinatorial problems. [pdf (arxiv)] [link]
  In Genetic and Evolutionary Computation Conference (GECCO 2011), pages 981-988, 2011. ACM.
  
  
• B. Doerr, M. Fouz.
  Asymptotically optimal rumor spreading. [pdf (arxiv)] [link]
  In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), pages 502-513, 2011. Springer Verlag.
  
  
• B. Doerr, C. Winzen.
  Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity. [pdf (arxiv)] [link]
  In Proceedings of 6th International Computer Science Symposium in Russia (CSR 2011), pages 15-28, 2011. Springer Verlag.
  
  
• B. Doerr, M. Fouz, T. Friedrich.
  Social networks spread rumors in sublogarithmic time. [pdf] [link]
  In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), pages 21-30, 2011. ACM.
  
  
• B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler.
  Stabilizing consensus with the power of two choices. [link]
  In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011), pages 149-158, 2011. ACM.
  
  
• M. Mainberger, S. Hoffmann, J. Weickert, C. H. Tang, D. Johannsen, F. Neumann, B. Doerr.
  Optimising spatial and tonal data for homogeneous diffusion inpainting. [pdf] [link]
  In Proceedings of the 3rd International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2011), pages 26-37, 2011. Springer Verlag.
  
  
• B. Doerr, M. Künnemann, M. Wahlström.
  Dependent randomized rounding: The bipartite case. [pdf]
  In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2011), pages 96-107, 2011. SIAM.
  
  
• B. Doerr, D. Johannsen, T. Kötzing, P. K. Lehre, M. Wagner, C. Winzen.
  Faster black-box algorithms through higher arity operators. [pdf (arxiv)] [link]
  In H.-G. Beyer, W. B. Langdon (Eds.), Proceedings of the Eleventh ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2011), pages 163-172, 2011. ACM.
  
  
• B. Doerr, D. Johannsen, M. Schmidt.
  Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets. [link]
  In H.-G. Beyer, W. B. Langdon (Eds.), Proceedings of the Eleventh ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2011), pages 119-126, 2011. ACM.
  
  
• B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler.
  Brief announcement: Stabilizing consensus with the power of two choices. [link]
  In N. A. Lynch, A. A. Shvartsman (Eds.), Proceedings of the 24th International Symposium on Distributed Computing 2010 (DISC 2010), volume 6343 of Lecture Notes in Computer Science, pages 528-530, 2010. Springer Verlag.
  
  
• B. Doerr, D. Johannsen, T. Kötzing, F. Neumann, M. Theile.
  More effective crossover operators for the all-pairs shortest path problem. [link]
  In R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature 2010, Part 1 (PPSN 2010), volume 6238 of Lecture Notes in Computer Science, pages 184-193, 2010. Springer-Verlag.
  
  
• B. Doerr, L. A. Goldberg.
  Drift analysis with tail bounds. [link]
  In R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature 2010, Part 1 (PPSN 2010), volume 6238 of Lecture Notes in Computer Science, pages 174-183, 2010. Springer Verlag.
  
  
• B. Doerr, T. Jansen, D. Sudholt, C. Winzen, C. Zarges.
  Optimizing monotone functions can be difficult. [pdf (arxiv)] [link]
  In R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature 2010, Part 1 (PPSN 2010), volume 6238 of Lecture Notes in Computer Science, pages 42-51, 2010. Springer Verlag.
  
  
• B. Doerr, L. A. Goldberg.
  Adaptive drift analysis. [pdf (arxiv)] [link]
  In R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature 2010, Part 1 (PPSN 2010), volume 6238 of Lecture Notes in Computer Science, pages 32-41, 2010. Springer Verlag.
  
  
• S. Böttcher, B. Doerr, F. Neumann.
  Optimal fixed and adaptive mutation rates for the LeadingOnes problem. [link]
  In R. Schaefer, C. Cotta, J. Kolodziej, G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature 2010, Part 1 (PPSN 2010), volume 6238 of Lecture Notes in Computer Science, pages 1-10, 2010. Springer Verlag.
  
  
• B. Doerr, D. Johannsen, C Winzen.
  Drift analysis and linear functions revisited. [pdf (arxiv)] [link]
  In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010), pages 1-8, 2010. IEEE.
  
  
• B. Doerr, M. Fouz, C. Witt.
  Quasirandom evolutionary algorithms. [link]
  In M. Pelikan, J. Branke (Eds.) Genetic and Evolutionary Computation Conference (GECCO 2010), pages 1457-1464, 2010. ACM.
  
  
• B. Doerr, D. Johannsen, C. Winzen.
  Multiplicative drift analysis. [pdf (arxiv)] [link]
  In M. Pelikan, J. Branke (Eds.) Genetic and Evolutionary Computation Conference (GECCO 2010), pages 1449-1456, 2010. ACM.
  Best paper award.
  
  
• B. Doerr, D. Johannsen.
  Edge-based representation beats vertex-based representation in shortest path problems. [link]
  In M. Pelikan, J. Branke (Eds.) Genetic and Evolutionary Computation Conference (GECCO 2010), pages 759-766, 2010. ACM.
  
  
• B. Doerr, M. Künnemann, M. Wahlström.
  Randomized rounding for routing and covering problems: Experiments and improvements. [pdf (arxiv)] [link]
  In P. Festa (Ed.), Proceedings of the 9th International Symposium on Experimental and Efficient Algorithms 2010 (SEA 2010), volume 6049 of Lecture Notes in Computer Science, pages 190-201, 2010. Springer Verlag.
  
  
• B. Doerr, A. Huber and A. Levavi.
  Strong robustness of randomized rumor spreading protocols. [pdf (arxiv)] [link]
  In Proceedings of the 20th International Symposium on Algorithms and Computation 2009 (ISAAC 2009), volume 5878 of Lecture Notes in Computer Science, pages 812-821, 2009. Springer Verlag.
  
  
• B. Doerr.
  Introducing quasirandomness to computer science. [link]
  Efficient Algorithms 2009, volume 5760 of Lecture Notes in Computer Science, pages 99-111, 2009. Springer Verlag.
  
  
• B. Doerr, M. Fouz, M. Schmidt, M. Wahlström.
  BBOB: Nelder-Mead with resize and halfruns. [link]
  In F. Rothlauf et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2009)(Companion Material), pages 2239-2246, 2009. ACM.
  
  
• B. Doerr, A. Eremeev, C. Horoba, F. Neumann, M. Theile.
  Evolutionary algorithms and dynamic programming. [link]
  In F. Rothlauf et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2009), pages 771-778, 2009. ACM.
  
  
• B. Doerr, M. Theile.
  Improved analysis methods for crossover-based algorithms. [link]
  In F. Rothlauf et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2009), pages 247-254, 2009. ACM.
  
  
• B. Doerr, T. Friedrich, T. Sauerwald.
  Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. [pdf] [link]
  In S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, W. Thomas (Eds.), Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), volume 5555 of Lecture Notes in Computer Science, pages 366-377, 2009. Springer Verlag.
  
  
• S. Baswana, S. Biswas, B. Doerr, T. Friedrich, P. P. Kurur, F. Neumann.
  Computing single source shortest paths using single-objective fitness functions. [pdf] [link]
  In I. Garibay, T. Jansen, R. P. Wiegand, and A. S. Wu (Eds.), Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2009), pages 59-66, 2009. ACM.
  
  
• B. Doerr, M. Wahlström.
  Randomized rounding in the presence of a cardinality constraint. [pdf]
  In I. Finocchi, J. Hershberger (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2009), pages 162-174, 2009. SIAM.
  
  
• B. Doerr, T. Friedrich, M. Künnemann, T. Sauerwald.
  Quasirandom rumor spreading: An experimental analysis. [pdf] [link]
  In I. Finocchi, J. Hershberger (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2009), pages 145-153, 2009. SIAM.
  
  
• B. Doerr, M. Gnewuch, M. Wahlström.
  Implementation of a component-by-component algorithm to generate small low-discrepancy samples. [pdf] [link]
  In P. L'Ecuyer, A. B. Owen (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, pages 323-338, 2009. Springer Verlag.
  
  
• B. Doerr, D. Johannsen, C. H. Tang.
  How single ant ACO Systems optimize pseudo-Boolean functions. [link]
  In Proceedings of PPSN 2008, pages 378-388. Springer Verlag.
  
  
• B. Doerr, Th. Jansen, C. Klein.
  Comparing local and global mutations on bit-strings. [preprint pdf] [link]
  In C. Ryan, M. Keijzer et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2008), pages 929-936, 2008. ACM.
  
  
• B. Doerr, E. Happ, C. Klein.
  Crossover can provably be useful in evolutionary computation. [preprint pdf] [link]
  In C. Ryan, M. Keijzer et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2008), pages 539-546, 2008. ACM.
  Best paper award.
  
  
• B. Doerr, E. Happ.
  Directed trees: A powerful representation for sorting and ordering problems. [preprint pdf] [link]
  In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008), pages 3606-3613, 2008. IEEE.
  
  
• B. Doerr, M. Gnewuch.
  Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. [pdf]
  In A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, pages 299-312, 2008. Springer Verlag.
  
  
• B. Doerr, T. Friedrich, T. Sauerwald.
  Quasirandom rumor spreading. [pdf] [link]
  In Proceedings of SODA 2008, pages 773-781. SIAM.
  
  
• J. Cooper, B. Doerr, T. Friedrich, J. Spencer.
  Deterministic random walks on regular trees. [pdf] [link]
  In Proceedings of SODA 2008, pages 766-772. SIAM.
  
  
• B. Doerr, E. Happ, C. Klein.
  A tight bound for the (1+1)-EA on the single source shortest path problem. [pdf] [link]
  In D. Srinivasan, L. Wang (Eds.), Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 1890-1895, 2007. IEEE.
  
  
• B. Doerr, M. Gnewuch, N. Hebbinghaus, F. Neumann.
  A rigorous view on neutrality. [link]
  In D. Srinivasan, L. Wang (Eds.), Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 2591-2597, 2007. IEEE.
  
  
• B. Doerr, D. Johannsen.
  Refined runtime analysis of a basic ant colony optimization algorithm. [link]
  In D. Srinivasan, L. Wang (Eds.), Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 501-507, 2007. IEEE.
  
  
• B. Doerr, D. Johannsen.
  Adjacency list matchings - An ideal genotype for cycle covers. [link]
  In D. Thierens et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2007), pages 1203-1210, 2007. ACM. Nominated for best paper award.
  
  
• B. Doerr, F. Neumann, D. Sudholt, C. Witt.
  On the runtime analysis of the 1-ANT ACO algorithm. [link]
  In D. Thierens et al. (Eds.), Genetic and Evolutionary Computation Conference (GECCO 2007), pages 33-40, 2007. ACM.
  Best paper award.
  
  
• B. Doerr, C. Klein, T. Storch.
  Faster evolutionary algorithms by superior graph representation. [pdf] [ps] [link]
  Proceedings of FOCI 2007, pages 245-250, 2007. IEEE.
  
  
• B. Doerr.
  Randomly rounding rationals with cardinality constraints and derandomizations. [pdf] [ps] [link]
  In W. Thomas, P. Weil (Eds.), Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS'07), volume 4393 of Lecture Notes in Computer Science, pages 441-452, 2007. Springer Verlag.
  
  
• B. Doerr, C. Klein.
  Unbiased rounding of rational matrices. [pdf] [link]
  In S. Arun-Kumar, N. Garg (Eds.), Proceedings of FSTTCS 2006, volume 4337 of Lecture Notes in Computer Science, pages 200-211, 2006. Springer Verlag.
  
  
• B. Doerr, T. Friedrich.
  Deterministic random walks on the two-dimensional grid. [pdf] [ps] [link]
  In T. Asano (Ed.), Proceedings of ISAAC 2006, volume 4288 of Lecture Notes in Computer Science, pages 474-483, 2006. Springer Verlag.
  
  
• B. Doerr, J. Lengler, D. Steurer.
  The interval liar game. [pdf] [ps][link]
  In T. Asano (Ed.), Proceedings of ISAAC 2006, volume 4288 of Lecture Notes in Computer Science, pages 318-327, 2006. Springer Verlag.
  
  
• B. Doerr, N. Hebbinghaus, F. Neumann.
  Speeding up evolutionary algorithms through restricted mutation operators. [pdf] [ps] [link]
  In T. P. Runarsson et al. (Eds.), Proceedings of PPSN 2006, volume 4193 of Lecture Notes in Computer Science, pages 978-987, 2006. Springer Verlag.
  
  
• B. Doerr, T. Friedrich, C. Klein, R. Osbild.
  Unbiased matrix rounding. [pdf] [ps] [link]
  In L. Arge, R. Freivalds (Eds.), Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), volume 4059 of Lecture Notes in Computer Science, pages 102-112, 2006. Springer Verlag.
  
  
• B. Doerr.
  Generating randomized roundings with cardinality constraints and derandomizations. [pdf] [ps] [link]
  In B. Durand, W. Thoas (Eds.), Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS'06), volume 3884 of Lecture Notes in Computer Science, pages 571-583, 2006. Springer Verlag.
  
  
• J. Cooper, B. Doerr, J. Spencer, G. Tardos.
  Deterministic random walks. [pdf] [ps]
  In Proceedings of the Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2006), pages 185-197, 2006. SIAM.
  
  
• S. Teramoto, T. Asano, B. Doerr, N. Katoh.
  Inserting points uniformly at every instance. [pdf] [ps] [link]
  In Korea-Japan Joint Workshop on Algorithms and Computation, pages 3-9, 2005.
  
  
• B. Doerr, T. Friedrich, C. Klein, R. Osbild.
  Rounding of sequences and matrices, with applications. [pdf] [ps] [link]
  In T. Erlebach, G. Persiano (Eds.), Proceedings of the Workshop on Approximation and Online Algorithms (WAOA 2005), volume 3879 of Lecture Notes in Computer Science, pages 96-109, 2006. Springer Verlag.
  
  
• N. Ahuja, A. Baltz, B. Doerr, A. Prívetivý, A. Srivastav.
  On the minimum load coloring problem. [pdf] [ps] [link]
  In T. Erlebach, G. Persiano (Eds.), Proceedings of the Workshop on Approximation and Online Algorithms (WAOA 2005), volume 3879 of Lecture Notes in Computer Science, pages 15-26, 2006. Springer Verlag.
  
  
• B. Doerr.
  Roundings respecting hard constraints. [pdf] [ps] [link]
  In V. Diekert, B. Durand (Eds.), Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS'05), volume 3404 of Lecture Notes in Computer Science, pages 617-628, 2005. Springer Verlag.
  
  
• B. Doerr.
  Matrix rounding with low error in small submatrices. [pdf] [ps] [link]
  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 1067-1068, 2005. SIAM.
  
  
• B. Doerr, N. Hebbinghaus, S. Werth.
  Improved bounds and schemes for the declustering problem. [pdf] [ps] [link]
  In J. Fiala, V. Koubek, J. Kratochvil (Eds.), Mathematical Foundations of Computer Science 2004, volume 3153 of Lecture Notes in Computer Science, pages 760-771, 2004. Springer Verlag.
  
  
• B. Doerr.
  Matrix rounding and approximation. [pdf] [ps] [link]
  In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pages 575-576, 2004. SIAM.
  
  
• B. Doerr.
  Non-independent randomized rounding. [pdf] [ps] [link]
  In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pages 506-507, 2003. SIAM.
  
  
• B. Doerr.
  Typical rounding problems. [pdf] [ps] [link]
  In K. Jansen, S. Leonardi, V. Vazirani (Eds.), Proceedings of APPROX 2002, volume 2462 of Lecture Notes in Computer Science, pages 81-93, 2002. Springer Verlag.
  
  
• B. Doerr, H. Schnieder.
  Non-independent randomized rounding and an application to digital halftoning. [pdf] [ps] [link]
  In R. Möhring, R. Raman (Eds.), Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), volume 2461 of Lecture Notes in Computer Science, pages 399-410, 2002. Springer Verlag.
  
  
• B. Doerr.
  Antirandomizing the wrong game. [pdf] [ps] [link]
  In R.Conejo, S. Eidenbenz, M. Hennessy, R. Morales, F. Triguero, P. Widmayer (Eds.), Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), volume 2380 of Lecture Notes in Computer Science, pages 876-887, 2002. Springer Verlag.
  
  
• B. Doerr.
  Balanced coloring: Equally easy for all numbers of colors? [pdf] [ps] [link]
  In H. Alt, A. Ferreira (Eds.), Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2002), volume 2285 of Lecture Notes in Computer Science, pages 112-120, 2002. Springer Verlag.
  
  
• B. Doerr.
  Structured randomized rounding and coloring. [pdf] [ps] [link]
  In R. Freivalds (Ed.), Fundamentals of Computation Theory, volume 2138 of Lecture Notes in Computer Science, pages 461-471, 2001. Springer Verlag.
  
  
• B. Doerr, A. Srivastav.
  Recursive randomized coloring beats fair dice random colorings. [pdf] [ps] [link]
  In A. Ferreira, H. Reichel (Eds.), Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS) 2001, volume 2010 of Lecture Notes in Computer Science, pages 183-194, 2001. Springer Verlag.
  
  
• B. Doerr.
  Lattice approximation and linear discrepancy of totally unimodular matrices. [pdf] [ps] [link]
  In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pages 119-125, 2001. SIAM.
  
  
• B. Doerr, A. Srivastav.
  Approximation of multi-color discrepancy. [pdf] [ps] [link]
  In D. Hochbaum et al. (Eds.), Randomization, Approximation and Combinatorial Optimization, volume 1671 of Lecture Notes in Computer Science, pages 39-50, 1999. Springer Verlag.
  
  

---

Short Abstracts in Refereed Proceedings

---

• B. Doerr, M. Fouz.
  Asymptotically optimal randomized rumor spreading. [pdf (arxiv)] [link]
  In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), ENDM 38, pages 297-302, 2011.
  
  
• B. Doerr, M. Fouz, T. Friedrich.
  Social networks spread rumors in sublogarithmic time. [link]
  In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), ENDM 38, pages 303-308, 2011.
  
  
• B. Doerr, M. Fouz
  A time-randomness tradeoff for quasi-random rumor spreading. [link]
  Electronic Notes in Discrete Mathematics Volume 34 (2009), pages 335-339.
  
  
• B. Doerr, T. Friedrich, T. Sauerwald.
  Quasirandom rumor spreading on expanders. [link]
  Electronic Notes in Discrete Mathematics Volume 34 (2009), pages 243-247.
  
  
• J. Cooper, B. Doerr, T. Friedrich, J. Spencer.
  Deterministic random walks on regular trees. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics Volume 29 (2007), pages 509-513.
  
  
• B. Doerr.
  Partial colorings of unimodular hypergraphs. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics, Volume 29 (2007), pages 359-363.
  
  
• B. Doerr, J. Lengler, D. Steurer.
  The interval liar game. [link]
  Electronic Notes in Discrete Mathematics, Volume 28 (2007), pages 425-432.
  
  
• T. Friedrich, B. Doerr, C. Klein, R. Osbild.
  Unbiased matrix rounding. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics, Volume 28 (2007), pages 41-46.
  
  
• B. Doerr, T. Friedrich.
  Quasirandomness in graphs. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics, Volume 25 (2006), pages 61-64.
  
  
• B. Doerr, C. Klein.
  Controlled randomized rounding. [link]
  In: U. Faigle, J.L. Hurink, F. Maffioli, R. Schrader, R. Schultz (Eds.), Proceedings of CTW2006 - Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Mathematics, Volume 25 (2006), pages 39-40.
  
  
• J. Cooper, B. Doerr, J. Spencer, G. Tardos.
  Deterministic random walks on the integers. [pdf] [ps] [link]
  In S. Felsner (Ed.), European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2005, volume AE of Discrete Mathematics & Theoretical Computer Science, pages 73-76.
  
  
• B. Doerr, M. Gnewuch, N. Hebbinghaus.
  Discrepancy of products of hypergraphs. [link]
  In S. Felsner (Ed.), European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2005, volume AE of Discrete Mathematics & Theoretical Computer Science, pages 323-328.
  
  
• B. Doerr.
  Multi-color discrepancies. [pdf] [ps]
  Oberwolfach Reports 1 (2004), 683-685. ISSN 1660-8933.
  
  
• B. Doerr, N. Hebbinghaus, S. Werth.
  An improved discrepancy approach to declustering. [pdf] [ps]
  Electronic Notes in Discrete Mathematics 17 (2004), 9-13.
  Also in L. Liberti, F. Maffioli (Eds.), Proceedings of CTW 2004, pages 114-118, 2004.
  
  
• N. Ahuja, A. Baltz, B. Doerr, A. Srivastav.
  Coloring graphs with minimal Edge load. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics 17 (2004), 129-133.
  In L. Liberti, F. Maffioli (Eds.), Proceedings of CTW 2004, pages 16-20, 2004.
  
  
• B. Doerr.
  Non-independent randomized rounding, linear discrepancy and an application to digital halftoning. [pdf] [ps]
  In J. Fiala (Ed.), Eurocomb '03, pages 95-99, Prague, 2003.
  
  
• B. Doerr.
  Vector balancing games with aging. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics, vol. 10, 2001.
  
  
• B. Doerr, A. Srivastav.
  Multi-color discrepancy of arithmetic progressions. [pdf] [ps]
  Electronic Notes in Discrete Mathematics, vol. 8, 2001.
  
  
• B. Doerr, A. Srivastav.
  Multi-color discrepancies. [pdf] [ps] [link]
  Electronic Notes in Discrete Mathematics, vol. 7, 2001.
  
  

---

Theses

---

• B. Doerr.
  Integral Approximation. [pdf] [ps]
  Habilitationsschrift. Christian-Albrechts-Universität zu Kiel, 2005.
  
  
• B. Doerr.
  Multi-Color Discrepancies. [pdf] [ps]
  Dissertation. Christian-Albrechts-Universität zu Kiel, 2000.
  
  
• B. Doerr.
  Nichtauflösbare J(T)-Komponenten. [pdf] [ps]
  Diplomarbeit. Christian-Albrechts-Universität zu Kiel, 1998.
  
  

• Benjamin Doerr:
• Publications
• Teaching
• CV
• Activities