Prof. Dr. Heiko Röglin

E-mail: roeglin(at)
Phone: +49 228 73 4326
Fax: +49 228 73 4321
Institute: Institute of Computer Science
Research Areas: Research Area I
Research Area KL
Former Research Area L
Date of birth: 10.Apr 1981
Mathscinet-Number: 781033

Academic Career


Dr. rer. nat., RWTH Aachen


Visiting Researcher, Microsoft Research Asia, Beijing, China

2008 - 2009

Postdoctoral Research Fellow, Boston University, MA, USA

2009 - 2010

Assistant Professor, Maastricht University, Netherlands

2010 - 2013

Professor (W2), University of Bonn

Since 2013

Professor (W3), University of Bonn

Research Profile

The focus of my current research lies on probabilistic analysis of algorithms for combinatorial optimization problems. It is a common phenomenon that the predominant concept of worst-case analysis yields too pessimistic results. Many algorithms are better (with respect to running time and quality of results) than such an analysis predicts because worst-case instances are often artificial and occur only rarely in applications. An important way to reduce the gap between theory and practice is to study the behavior of algorithms on random or randomly perturbed inputs. For many algorithms such a probabilistic analysis reveals that worst-case instances are fragile and not robust against random noise. We have shown, for example, that the expected running time of simple local search heuristics on randomly perturbed inputs is in many cases polynomial despite their very bad worst-case behavior. These results provide the first rigorous explanation for the practical success of local search for the traveling salesman problem and other important optimization problems.

Probabilistic analysis of algorithm is a research area with many interesting and challenging open questions. I will continue my work in this area. While at the moment many ad-hoc methods are used, I plan to devise and study more general methods for the analysis of algorithms on randomly perturbed inputs in order to unify existing results and to broaden the range of applications. The insights gained from probabilistic analyses shall also lead to the design of better algorithms and techniques. As an example, better bounds on the diameter of totally unimodular polytopes were already proved using these insights.

Research Projects and Activities

ERC Starting Grant “Algorithms beyond the Worst Case”

ACM Conference on Economics and Computation (2011, 2014, 2016)
Program committee member

Conference on Web and Internet Economics (2012)
Program committee member

Symposium on Theoretical Aspects of Computer Science (2014)
Program committee member

DFG Cluster of Excellence “Hausdorff Center for Mathematics”

Selected Publications

[1] Tobias Brunsch, Anna Groß wendt, Heiko Röglin
Solving totally unimodular LPs with the shadow vertex algorithm
32nd International Symposium on Theoretical Aspects of Computer Science
of LIPIcs. Leibniz Int. Proc. Inform. : 171--183
Publisher: Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern
[2] Michael Etscheid, Heiko Röglin
Smoothed analysis of local search for the maximum-cut problem
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher: ACM, New York
DOI: 10.1137/1.9781611973402.66
[3] Tobias Brunsch, Heiko Röglin
Finding short paths on polytopes by the shadow vertex algorithm
Automata, languages, and programming. Part I
of Lecture Notes in Comput. Sci. : 279--290
Publisher: Springer, Heidelberg
DOI: 10.1007/978-3-642-39206-1_24
[4] Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner
Smoothed analysis of the successive shortest path algorithm
SIAM J. Comput. , 44: (6): 1798--1819
DOI: 10.1137/140989893
[5] Tobias Brunsch, Heiko Röglin
Improved smoothed analysis of multiobjective optimization
J. ACM , 62: (1): Art. 4, 58
DOI: 10.1145/2699445
[6] Heiko Röglin, Shang-Hua Teng
Smoothed analysis of multiobjective optimization
2009 50th Annual IEEE Symposium on Foundations of Computer Science---FOCS 2009
Publisher: IEEE Computer Soc., Los Alamitos, CA
DOI: 10.1109/FOCS.2009.21
[7] David Arthur, Bodo Manthey, Heiko Röglin
Smoothed analysis of the k-means method
J. ACM , 58: (5): Art. 19, 31
DOI: 10.1145/2027216.2027217
[8] Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking
Uncoordinated two-sided matching markets
SIAM J. Comput. , 40: (1): 92--106
DOI: 10.1137/090753498
[9] Matthias Englert, Heiko Röglin, Berthold Vöcking
Worst case and probabilistic analysis of the 2-opt algorithm for the TSP
Algorithmica , 68: (1): 190--264
DOI: 10.1007/s00453-013-9801-4
[10] Heiner Ackermann, Heiko Röglin, Berthold Vöcking
On the impact of combinatorial structure on congestion games
J. ACM , 55: (6): Art. 25, 22
DOI: 10.1145/1455248.1455249

Publication List



Outstanding Paper Award of the 9th ACM Conference on Electronic Commerce


Best Paper Award of the 7th International Conference on Swarm Intelligence


ERC Starting Grant


Teaching Award of the University of Bonn

Selected Invited Lectures


38th Conference on the Mathematics of Operations Research, Lunteren, Netherlands



Professor (W3), TU Hamburg

Selected PhD students

Tobias Brunsch (2014): “Smoothed Analysis of Selected Optimization Problems and Algorithms”

Supervised Theses

  • Master theses: 3
  • Diplom theses: 5
  • PhD theses: 5, currently 4
Download Profile