Probabilistic analysis of algorithms, smoothed analysis
Randomized algorithms
Graph theory
Publications
Tobias Brunsch and Heiko Röglin.
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm.
In Proc. of the 40th ICALP (Riga, Latvia), pp. 279-290 (Part 1), 2013.
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, and Heiko Röglin.
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching.
In Proc. of the 7th WALCOM (Kharagpur, India), pp. 182-193, 2013. Als PDF anschauen
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, and Heiko Röglin.
Smoothed Analysis of the Successive Shortest Path Algorithm.
In Proc. of the 24th SODA (New Orleans, USA), pp. 1180-1189, 2013. Als PDF anschauen
Tobias Brunsch and Heiko Röglin.
Improved Smoothed Analysis of Multiobjective Optimization.
In Proc. of the 44th STOC (New York, USA), pp. 407-426, 2012. Als PDF anschauen
Tobias Brunsch, Heiko Röglin, Cyriel Rutten, and Tjark Vredeveld.
Smoothed Performance Guarantees for Local Search.
In Proc. of the 19th ESA (Saarbrücken, Germany), pp. 772-783, 2011.
Erschien auch in Mathematical Programming A, 2013. Als PDF anschauen
Tobias Brunsch and Heiko Röglin.
Lower Bounds for the Smoothed Number of Pareto optimal Solutions. In Proc. of the 8th TAMC (Tokyo, Japan), pp. 416-427, 2011. Als PDF anschauen