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
[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.
 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 to appear 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 to appear 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 to appear 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.
 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 to appear 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
[J13]
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia.
Active Clustering of Biological Sequences.
To appear in Journal of Machine Learning Research.
 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), 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.
To appear in Networks.
 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
[TR3]
Tobias Brunsch and Heiko Röglin.
Improved Smoothed Analysis of Multiobjective Optimization.
CoRR, November 2011.
 arxiv
[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.