|
|
|
| 2008 | Dr. rer. nat., RWTH Aachen | | 2008 | 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 |
|
|
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.
|
|
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”
Member
Associate Editor
of SIAM Journal on Discrete Mathematics
|
|
[ 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
2015[ 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
2014
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
2013
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
2015
DOI: 10.1137/140989893[ 5] Tobias Brunsch, Heiko Röglin
Improved smoothed analysis of multiobjective optimization
J. ACM , 62: (1): Art. 4, 58
2015
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
2009
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
2011
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
2011
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
2014
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
2008
DOI: 10.1145/1455248.1455249 |
|
|
|
|
|
|
|
| 2008 | Outstanding Paper Award of the 9th ACM Conference on Electronic Commerce | | 2010 | Best Paper Award of the 7th International Conference on Swarm Intelligence | | 2012 | ERC Starting Grant | | 2015 | Teaching Award of the University of Bonn |
|
|
| 2013 | 38th Conference on the Mathematics of Operations Research, Lunteren, Netherlands |
|
|
| 2013 | Professor (W3), TU Hamburg |
|
|
|
Tobias Brunsch (2014): “Smoothed Analysis of Selected Optimization Problems and Algorithms”
|
|
- Master theses: 30
- Diplom theses: 5
- PhD theses: 5, currently 4
|
|
Download Profile  |
