Heiko Röglin

Publications (dblp, Google Scholar)

[Conferences]   [Journals]   [Technical Reports]   [Other Publications]
The versions you can download here do not necessarily coincide with the original publications, which can be found by following the links.
Papers in Conference Proceedings
[C32]
Michael Etscheid and Heiko Röglin
Smoothed Analysis of Local Search for the Maximum-Cut Problem
In Proc. of the 25th SODA (Portland, USA), pp. 882-889, 2014.
WWW   PDF
[C31]
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, 2013.
WWW   PDF
[C30]
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.
Also appeared in special issue of Journal of Graph Algorithms and Applications (see [J19]).
WWW   PDF
[C29]
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.
WWW   PDF
[C28]
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.
WWW   PDF
[C27]
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.
Also appeared in Mathematical Programming (see [J16]).
WWW   PDF
[C26]
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia
Min-Sum Clustering of Protein Sequences with Limited Distance Information
In Proc. of the 1st SIMBAD (Venice, Italy), pp. 192-206, 2011.
WWW   PDF
[C25]
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.
Also appeared in Theory of Computing (see [J20]).
WWW   PDF
[C24]
Tobias Brunsch and Heiko Röglin
A Bad Instance for k-means++
In Proc. of the 8th TAMC (Tokyo, Japan), pp. 344-352, 2011.
Also appeared in special issue of Theoretical Computer Science (see [J14]).
WWW   PDF
[C23]
Andre Berger, Heiko Röglin, and Ruben van der Zwaan
Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results
In Proc. of the 10th SEA (Crete, Greece), pp. 43-53, 2011.
WWW   PDF
[C22]
Patrick Briest and Heiko Röglin
The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers
In Proc. of the 8th WAOA (Liverpool, U.K.), pp. 47-58, 2010.
WWW   PDF
[C21]
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia
Efficient Clustering with Limited Distance Information
In Proc. of the 26th UAI (Catalina Island, USA), pp. 632-641, 2010.
Also appeared in Journal of Machine Learning Research (see [J13]).
WWW   PDF
[C20]
Timo Kötzing, Frank Neumann, Heiko Röglin, and Carsten Witt
Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem
In Proc. of the 7th ANTS (Brussels, Belgium), pp. 324-335, 2010.
Also appeared in Swarm Intelligence (see [J12]).
Best Paper Award of ANTS 2010
WWW   PDF
[C19]
Martin Hoefer, Vahab Mirrokni, Heiko Röglin, and Shang-Hua Teng
Competitive Routing over Time
In Proc. of the 5th WINE (Rome, Italy), pp. 18-29, 2009.
Also appeared in Theoretical Computer Science (see [J9]).
WWW   PDF
[C18]
Bodo Manthey and Heiko Röglin
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
In Proc. of the 20th ISAAC (Hawaii, USA), pp. 1024-1033, 2009.
Also appeared in Journal of Computational Geometry (see [J18]).
WWW   PDF
[C17]
Heiko Röglin and Shang-Hua Teng
Smoothed Analysis of Multiobjective Optimization
In Proc. of the 50th FOCS (Atlanta, USA), pp. 681-690, 2009.
WWW   PDF
[C16]
David Arthur, Bodo Manthey, and Heiko Röglin
k-Means has Polynomial Smoothed Complexity
In Proc. of the 50th FOCS (Atlanta, USA), pp. 405-414, 2009.
Also appeared in Journal of the ACM (see [J11]).
WWW   PDF
[C15]
Maria-Florina Balcan, Heiko Röglin, and Shang-Hua Teng
Agnostic Clustering
In Proc. of the 20th ALT (Porto, Portugal), pp. 384-398, 2009.
WWW   PDF
[C14]
Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking
Economical Caching
In Proc. of the 26th STACS (Freiburg, Germany), pp. 385-396, 2009.
Also appeared in ACM Transactions on Computation Theory (see [J15]).
WWW   PDF
[C13]
Bodo Manthey and Heiko Röglin
Improved Smoothed Analysis of the k-Means Method
In Proc. of the 20th SODA (New York, USA), pp. 461-470, 2009.
WWW   PDF
[C12]
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking
Uncoordinated Two-Sided Matching Markets
In Proc. of the 9th EC (Chicago, USA), pp. 256-263, 2008.
Also appeared in SIAM Journal on Computing (see [J7]).
Outstanding Paper Award of EC 2008
WWW   PDF
[C11]
Andreas Emil Feldmann, Heiko Röglin, and Berthold Vöcking
Computing Approximate Nash Equilibria in Network Congestion Games
In Proc. of the 15th SIROCCO (Villars-sur-Ollon, Switzerland), pp. 209-220, 2008.
Also appeared in Networks (see [J8]).
WWW   PDF
[C10]
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking
A Unified Approach to Congestion Games and Two-Sided Markets
In Proc. of the 3rd WINE (San Diego, USA), pp. 30-41, 2007.
Also appeared in special issue of Internet Mathematics (see [J4]).
WWW   PDF
[C9]
Rene Beier, Heiko Röglin, and Berthold Vöcking
The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
In Proc. of the 12th IPCO (Ithaca, USA), pp. 53-67, 2007.
WWW   PDF
[C8]
Matthias Englert, Heiko Röglin, and Berthold Vöcking
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
In Proc. of the 18th SODA (New Orleans, USA), pp. 1295-1304, 2007.
Also appeared in Algorithmica (see [J17]).
WWW   PDF
[C7]
Heiner Ackermann, Heiko Röglin, and Berthold Vöcking
Pure Nash Equilibria in Player-Specific and Weighted Congestion Games
In Proc. of the 2nd WINE (Patras, Greece), pp. 50-61, 2006.
Also appeared in special issue of Theoretical Computer Science (see [J5]).
WWW   PDF
[C6]
Heiner Ackermann, Heiko Röglin, and Berthold Vöcking
On the Impact of Combinatorial Structure on Congestion Games
In Proc. of the 47th FOCS (Berkeley, USA), pp. 613-622, 2006.
Also appeared in Journal of the ACM (see [J3]).
WWW   PDF
[C5]
Matthias Englert, Heiko Röglin, and Matthias Westermann
Evaluation of Online Strategies for Reordering Buffers
In Proc. of the 5th WEA (Menorca Island, Spain), pp. 183-194, 2006.
Also appeared in special issue of ACM Journal of Experimental Algorithmics (see [J6]).
WWW   PDF
[C4]
Heiner Ackermann, Alantha Newman, Heiko Röglin, and Berthold Vöcking
Decision Making Based on Approximate and Smoothed Pareto Curves
In Proc. of the 16th ISAAC (Sanya, China), pp. 675-684, 2005.
Also appeared in special issue of Theoretical Computer Science (see [J2]).
WWW   PDF
[C3]
Heiko Röglin and Berthold Vöcking
Smoothed Analysis of Integer Programming
In Proc. of the 11th IPCO (Berlin, Germany), pp. 276-290, 2005.
Also appeared in special issue of Mathematical Programming (see [J1]).
WWW   PDF
[C2]
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener
The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
In Proc. of the 8th PPSN (Birmingham, UK), pp. 31-40, 2004.
WWW   PDF
[C1]
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener
Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization
In Proc. of the 8th PPSN (Birmingham, UK), pp. 21-30, 2004.
WWW   PDF
Articles in Journals
[J20]
Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
To appear in Theory of Computing.
[J19]
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, and Heiko Röglin
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
Journal of Graph Algorithms and Applications, 17(6):647-670, 2013.
WWW   PDF
[J18]
Bodo Manthey and Heiko Röglin
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
Journal of Computational Geometry, 4(1):94-132, 2013.
WWW   PDF
[J17]
Matthias Englert, Heiko Röglin, and Berthold Vöcking
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Algorithmica, 68(1): 190-264, 2014.
WWW   PDF
[J16]
Tobias Brunsch, Heiko Röglin, Cyriel Rutten, and Tjark Vredeveld
Smoothed Performance Guarantees for Local Search
To appear in Mathematical Programming.
WWW   PDF
[J15]
Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking
Economical Caching
ACM Transactions on Computation Theory, 5(2), 2013.
WWW   PDF
[J14]
Tobias Brunsch and Heiko Röglin
A Bad Instance for k-means++
Theoretical Computer Science, 505:19-26, 2013.
WWW   PDF
[J13]
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia
Active Clustering of Biological Sequences
Journal of Machine Learning Research, 13:203-225, 2012.
WWW   PDF
[J12]
Timo Kötzing, Frank Neumann, Heiko Röglin, and Carsten Witt
Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem
Swarm Intelligence, 6(1):1-21, 2012.
WWW   PDF
[J11]
David Arthur, Bodo Manthey, and Heiko Röglin
Smoothed Analysis of the k-Means Method
Journal of the ACM, 58(5), 2011.
WWW   PDF
[J10]
Bodo Manthey and Heiko Röglin
Smoothed Analysis: Analysis of Algorithms Beyond Worst Case
it - Information Technology, 53(6):280-286, 2011.
WWW  
[J9]
Martin Hoefer, Vahab Mirrokni, Heiko Röglin, and Shang-Hua Teng
Competitive Routing over Time
Theoretical Computer Science, 412(39):5420-5432, 2011.
WWW   PDF
[J8]
Andreas Emil Feldmann, Heiko Röglin, and Berthold Vöcking
Computing Approximate Nash Equilibria in Network Congestion Games
Networks, 59(4):380-386, 2012.
WWW   PDF
[J7]
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking
Uncoordinated Two-Sided Matching Markets
SIAM Journal on Computing, 40(1):92-106, 2011.
WWW   PDF
[J6]
Matthias Englert, Heiko Röglin, and Matthias Westermann
Evaluation of Online Strategies for Reordering Buffers
ACM Journal of Experimental Algorithmics, 14, 2009.
WWW   PDF
[J5]
Heiner Ackermann, Heiko Röglin, and Berthold Vöcking
Pure Nash Equilibria in Player-Specific and Weighted Congestion Games
Theoretical Computer Science, 410(17):1552-1563, 2009.
WWW   PDF
[J4]
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking
A Unified Approach to Congestion Games and Two-Sided Markets
Internet Mathematics, 5(4):439-457, 2008.
WWW   PDF
[J3]
Heiner Ackermann, Heiko Röglin, and Berthold Vöcking
On the Impact of Combinatorial Structure on Congestion Games
Journal of the ACM, 55(6), 2008.
WWW   PDF
[J2]
Heiner Ackermann, Alantha Newman, Heiko Röglin, and Berthold Vöcking
Decision Making Based on Approximate and Smoothed Pareto Curves
Theoretical Computer Science, 378(3):253-270, 2007.
WWW   PDF
[J1]
Heiko Röglin and Berthold Vöcking
Smoothed Analysis of Integer Programming
Mathematical Programming, 110(1):21-56, 2007.
WWW   PDF
Technical Reports
[TR2]
Heiner Ackermann and Heiko Röglin
On the Convergence Time of the Best Response Dynamics in Player-specific Congestion Games
CoRR, May 2008.
arxiv
[TR1]
Patrick Briest, Paul Goldberg, and Heiko Röglin
Approximate Equilibria in Games with Few Players
CoRR, April 2008.
arxiv
Other Publications
[M4]
Heiner Ackermann, Heiko Röglin, Ulf Schellbach, and Nils Schweer
Analysis of Algorithms
Book chapter in Algorithm Engineering, pp. 127-193, Springer, 2010.
WWW
[M3]
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking
Uncoordinated Two-Sided Matching Markets
SIGecom Exchanges, 8(1), July 2009.
WWW
[M2]
Heiko Röglin
The Complexity of Nash Equilibria, Local Optima, and Pareto-Optimal Solutions
PhD Thesis, RWTH Aachen University, April 2008.
PDF
[M1]
Heiko Röglin
Probabilistische Analyse ganzzahliger Programmierung
Diploma Thesis (in German), University of Dortmund, August 2004.
PDF