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
[C50]
Frederik Brüning, Anne Driemel, Alperen Ergür, Heiko Röglin
On the number of iterations of the DBA algorithm
To appear in Proc. of the 24th SDM, 2024.
[C49]
Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt, and Julian Wargalla
Connected k-Center and k-Diameter Clustering
In Proc. of the 50th ICALP, pp. 50:1-50:20, 2023.
WWW   PDF
[C48]
Anna Arutyunova and Heiko Röglin
The Price of Hierarchical Clustering
In Proc. of the 30th ESA, pp. 10:1-10:14, 2022.
WWW   PDF
[C47]
Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin
Minimum-Error Triangulations for Sea Surface Reconstruction
In Proc. of the 38th SoCG, pp. 7:1-7:18, 2022.
Also appeared in Journal of Computational Geometry (see [J31]).
WWW
[C46]
Anna Arutyunova, Anna Großwendt, Heiko Röglin, Melanie Schmidt, and Julian Wargalla
Upper and Lower Bounds for Complete Linkage in General Metric Spaces
In Proc. of the 24th Approx, pp. 18:1-18:22, 2021.
Also appeared in Machine Learning (see [J32]).
WWW
[C45]
Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, and Jan-Henrik Haunert
Bicriteria Aggregation of Polygons via Graph Cuts
In Proc. of the 11th GIScience, pp. 6:1-6:16,2021.
WWW
[C44]
Anup Bhattacharya, Jan Eube, Heiko Röglin, and Melanie Schmidt
Noisy, Greedy and Not So Greedy k-means++
In Proc. of the 28th ESA (Pisa, Italy), pp. 18:1-18:21, 2020.
WWW
[C43]
Anna Großwendt, Heiko Röglin, and Melanie Schmidt
Analysis of Ward's Method
In Proc. of the 30th SODA (San Diego, USA), pp. 2939-2957, 2019.
WWW   PDF
[C42]
Carsten Fischer and Heiko Röglin
Probabilistic Analysis of (Class-constrained) Bin Packing and Bin Covering
In Proc. of the 13th LATIN (Buenos Aires, Argentina), pp. 461-474, 2018.
WWW   PDF
[C41]
Heiko Röglin and Clemens Rösner
The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization
In Proc. of the 14th TAMC (Bern, Switzerland), pp. 543-555, 2017.
Also appeared in Mathematical Programming (see [J30]).
WWW   PDF
[C40]
Tobias Brunsch, Michael Etscheid, and Heiko Röglin
Bounds for the Convergence Time of Local Search in Scheduling Problems
In Proc. of the 12th WINE (Montreal, Canada), pp. 339-353, 2016.
WWW   PDF
[C39]
Alantha Newman, Heiko Röglin, and Johanna Seif
The Alternating Stock Size Problem and the Gasoline Puzzle
In Proc. of the 24th ESA (Aarhus, Denmark), pp. 71:1-71:16, 2016.
Also appeared in ACM Transactions on Algorithms (see [J28]).
WWW   PDF
[C38]
Carsten Fischer and Heiko Röglin
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 469-482, 2016.
WWW   PDF
[C37]
Matthias Mnich, Heiko Röglin, and Clemens Rösner
New Deterministic Algorithms for Solving Parity Games
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 634-645, 2016.
Also appeared in Discrete Optimization (see [J29]).
WWW   PDF
[C36]
Anna Großwendt and Heiko Röglin
Improved Analysis of Complete-Linkage Clustering
In Proc. of the 23rd ESA (Patras, Greece), pp. 656-667, 2015.
Also appeared in special issue of Algorithmica (see [J27]).
WWW   PDF
[C35]
Michael Etscheid and Heiko Röglin
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
In Proc. of the 23rd ESA (Patras, Greece), pp. 509-520, 2015.
WWW   PDF
[C34]
Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin
Polynomial Kernels for Weighted Problems
In Proc. of the 40th MFCS (Milano, Italy), pp. 287-298, 2015.
Also appeared in Journal of Computer and System Sciences (see [J25]).
WWW   PDF
[C33]
Tobias Brunsch, Anna Großwendt, and Heiko Röglin
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
In Proc. of the 32nd STACS (Munich, Germany), pp. 171-183, 2015.
WWW   PDF
[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 [J17]).
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.
Also appeared in SIAM Journal on Computing (see [J23]).
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.
Also appeared in Journal of the ACM (see [J21]).
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 [J18]).
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.
Also appeared in Discrete Applied Mathematics (see [J22]).
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 [J16]).
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 [J8]).
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 [J11]).
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.
Also appeared in Mathematical Programming (see [J30]).
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 parts in Algorithmica (see [J19]).
Also appeared in parts in ACM Transactions on Algorithms (see [J24]).
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
[J32]
Anna Arutyunova, Anna Großwendt, Heiko Röglin, Melanie Schmidt, and Julian Wargalla
Upper and Lower Bounds for Complete Linkage in General Metric Spaces
Machine Learning, 113:489–518, 2024.
WWW
[J31]
Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin
Minimum-Error Triangulations for Sea Surface Reconstruction
Journal of Computational Geometry, 14(2):108-171, 2023.
WWW
[J30]
Rene Beier, Heiko Röglin, Clemens Rösner, and Berthold Vöcking
The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization
Mathematical Programming, 200(1):319-355, 2023.
WWW
[J29]
Matthias Mnich, Heiko Röglin, and Clemens Rösner
New Deterministic Algorithms for Solving Parity Games
Discrete Optimization, 30:73-95, 2018.
WWW   PDF
[J28]
Alantha Newman, Heiko Röglin, and Johanna Seif
The Alternating Stock Size Problem and the Gasoline Puzzle
ACM Transactions on Algorithms, 14(2):19:1-19:23, 2018.
WWW   PDF
[J27]
Anna Großwendt and Heiko Röglin
Improved Analysis of Complete-Linkage Clustering
Algorithmica, 78(4):1131-1150, 2017.
WWW   PDF
[J26]
Michael Etscheid and Heiko Röglin
Smoothed Analysis of Local Search for the Maximum-Cut Problem
ACM Transactions on Algorithms, 13(2), 2017.
WWW   PDF
[J25]
Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin
Polynomial Kernels for Weighted Problems
Journal of Computer and System Sciences, 84:1-10, 2017.
WWW   PDF
[J24]
Matthias Englert, Heiko Röglin, and Berthold Vöcking
Smoothed Analysis of the 2-Opt Algorithm for the General TSP
ACM Transactions on Algorithms, 13(1), 2016.
WWW   PDF
[J23]
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, and Clemens Rösner
Smoothed Analysis of the Successive Shortest Path Algorithm
SIAM Journal on Computing, 44(6):1798-1819, 2015.
WWW   PDF
[J22]
Andre Berger, Heiko Röglin, and Ruben van der Zwaan
Internet Routing between Autonomous Systems: Fast Algorithms for Path Trading
Discrete Applied Mathematics, 185:8-17, 2015.
WWW   PDF
[J21]
Tobias Brunsch and Heiko Röglin
Improved Smoothed Analysis of Multiobjective Optimization
Journal of the ACM, 62(1), 2015.
WWW   PDF
[J20]
Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
Theory of Computing, 10(10):237-256, 2014.
WWW  
[J19]
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
[J18]
Tobias Brunsch, Heiko Röglin, Cyriel Rutten, and Tjark Vredeveld
Smoothed Performance Guarantees for Local Search
Mathematical Programming, 146(1-2):185-218, 2014.
WWW   PDF
[J17]
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
[J16]
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
[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]
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
[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]
David Arthur, Bodo Manthey, and Heiko Röglin
Smoothed Analysis of the k-Means Method
Journal of the ACM, 58(5), 2011.
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
[M6]
Heiko Röglin
Smoothed Analysis of Pareto Curves in Multiobjective Optimization
Book chapter in Beyond the Worst-Case Analysis of Algorithms, pp. 334-358, Cambridge University Press , 2020.
WWW   PDF
[M5]
Heiko Röglin
Smoothed Analysis
Book chapter in Encyclopedia of Algorithms 2016, pp. 2014-2017, Springer, 2016.
WWW
[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