Heiko Röglin

Publications (dblp, Google Scholar)

[Conferences]   [Journals]   [Technical Reports]   [Theses]
The versions you can download here are the most recent ones; they do not necessarily coincide with the original publications, which can be found by following the links.
Papers in Conference Proceedings
[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.
 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.
 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.
 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.
 arxiv
[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.
 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   arxiv
[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.
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.
 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.
Invited to a special issue of Internet Mathematics (see [J5]).
 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.
 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.
Invited to a special issue of Theoretical Computer Science (see [J4]).
 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.
Invited to a 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.
Invited to a 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.
Invited to a 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
[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, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking.
A Unified Approach to Congestion Games and Two-Sided Markets.
To appear in Internet Mathematics.
 PDF
[J4]
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
[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.
 arxiv
[TR1]
Patrick Briest, Paul Goldberg, and Heiko Röglin.
Approximate Equilibria in Games with Few Players.
 arxiv
Theses
[T2]
Heiko Röglin.
The Complexity of Nash Equilibria, Local Optima, and Pareto-Optimal Solutions.
PhD Thesis, RWTH Aachen University, April 2008.
 PDF
[T1]
Heiko Röglin.
Probabilistische Analyse ganzzahliger Programmierung.
Diploma Thesis (in German), University of Dortmund, August 2004.
 PDF

© Copyright Notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.