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
[C31]
Tobias Brunsch and Heiko Röglin.
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm.
To appear in Proc. of the 40th ICALP (Riga, Latvia), 2013.
 arxiv
[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.
 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   arxiv
[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.
 WWW   arxiv
[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   arxiv
[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.
 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 to appear in 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   arxiv
[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.
Best Paper Award of ANTS 2010.
Also appeared in Swarm Intelligence (see [J12]).
 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.
 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   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.
Also to appear 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   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.
Also appeared in SIAM Journal on Computing (see [J7]).
 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.
Invited to a 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.
 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 [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.
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
[J16]
Tobias Brunsch, Heiko Röglin, Cyriel Rutten, and Tjark Vredeveld.
Smoothed Performance Guarantees for Local Search.
To appear in Mathematical Programming.
 WWW   arxiv
[J15]
Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking.
Economical Caching.
To appear in ACM Transactions on Computation Theory.
 PDF
[J14]
Tobias Brunsch and Heiko Röglin.
A Bad Instance for k-means++.
To appear in Theoretical Computer Science.
 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   arxiv
[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   arxiv
[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

© 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.