My Research

My interests are best described as design and analysis of practical algorithms and data structures using methods from my rigorous theory background. That is, I want to find solutions to algorithmic problems that work in practice, and analyze them as rigorously as possible in a suitable model.

The goal is that results of formal analysis can predict real behavior at least relatively so that we can check hypotheses with experiments. The methods championed by Donald E. Knuth, Robert Sedgewick and Philippe Flajolet seem to be of particular use in this regard.

One particular interest of mine is doing the above for parallel settings. This has yet to bear concrete fruit.

Other than that, I regularly get nerd-sniped by other interesting problems and questions of folklore, both of which abound in the field.

I have collected some open questions.


  1. Raphael Reitzig and Sebastian Wild: A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment, ArXiv e-prints. 2015.

  2. Raphael Reitzig and Sebastian Wild: Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks, Algorithmica, 80(11) . : 3365–3396, 2018. DOI: 10.1007/s00453-017-0392-3.

  3. S. Wild et al.: Engineering Java 7’s Dual Pivot Quicksort Using MaLiJan, Meeting on Algorithm Engineering & Experiments (ALENEX) (2013), DOI: 10.1137/1.9781611972931.5.

  4. Raphael Reitzig: Automated Parallelisation of Dynamic Programming Recursions, Master's thesis. University of Kaiserslautern, 2012.

  5. M. E. Nebel et al.: JAguc – a Software Package for Environmental Diversity Analyses, Journal of Bioinformatics and Computational Biology 9(6) (2011): 749–773, DOI: 10.1142/S0219720011005781.

  6. Raphael Reitzig: Ambiguity Analysis of RNA Secondary Structure Prediction Grammars. Bachelor’s thesis, 2009.

My Research - Raphael Reitzig