Heiko Röglin

Follow

Generating author description...

All published works
Action Title Year Authors
+ PDF Chat Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously 2025 Matthias Kaul
Kelin Luo
Matthias Mnich
Heiko Röglin
+ On the number of iterations of the DBA algorithm 2024 Frederik Brüning
Anne Driemel
Alperen A. Ergür
Heiko Röglin
+ PDF Chat On the number of iterations of the DBA algorithm 2024 Frederik Brüning
Anne Driemel
Alperen A. Ergür
Heiko Röglin
+ PDF Chat Upper and lower bounds for complete linkage in general metric spaces 2023 Anna Arutyunova
Anna Großwendt
Heiko Röglin
Melanie Schmidt
Julian Wargalla
+ Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP 2023 Matthias Englert
Heiko Röglin
Berthold Vöcking
+ Minimum-Error Triangulations for Sea Surface Reconstruction 2022 Anna Arutyunova
Anne Driemel
Jan‐Henrik Haunert
Herman Haverkort
Jürgen Kusche
Elmar Langetepe
Philip R. Mayer
Petra Mutzel
Heiko Röglin
+ The Price of Hierarchical Clustering 2022 Anna Arutyunova
Heiko Röglin
+ Connected k-Center and k-Diameter Clustering 2022 Lukas Drexler
Jan Eube
Kelin Luo
Heiko Röglin
Melanie Schmidt
Julian Wargalla
+ PDF Chat Smoothed Analysis of Pareto Curves in Multiobjective Optimization 2020 Heiko Röglin
+ Smoothed Analysis of Pareto Curves in Multiobjective Optimization 2020 Heiko Röglin
+ Smoothed Analysis of Pareto Curves in Multiobjective Optimization 2020 Heiko Röglin
+ Analysis of ward's method 2019 Anna Großwendt
Heiko Röglin
Melanie Schmidt
+ Noisy, Greedy and Not So Greedy k-means++ 2019 Anup Bhattacharya
Jan Eube
Heiko Röglin
Melanie Schmidt
+ Analysis of Ward's Method 2019 Anna Großwendt
Heiko Röglin
Melanie Schmidt
+ New deterministic algorithms for solving parity games 2018 Matthias Mnich
Heiko Röglin
Clemens Rösner
+ PDF Chat The Alternating Stock Size Problem and the Gasoline Puzzle 2018 Alantha Newman
Heiko Röglin
Johanna Seif
+ PDF Chat Polynomial kernels for weighted problems 2016 Michael Etscheid
Stefan Kratsch
Matthias Mnich
Heiko Röglin
+ PDF Chat New Deterministic Algorithms for Solving Parity Games 2016 Matthias Mnich
Heiko Röglin
Clemens Rösner
+ PDF Chat Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering 2016 Carsten Fischer
Heiko Röglin
+ Smoothed Analysis 2016 Heiko Röglin
+ Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering 2015 Carsten Fischer
Heiko Röglin
+ New Deterministic Algorithms for Solving Parity Games 2015 Matthias Mnich
Heiko Röglin
Clemens Rösner
+ Polynomial Kernels for Weighted Problems 2015 Michael Etscheid
Stefan Kratsch
Matthias Mnich
Heiko Röglin
+ PDF Chat Improved Smoothed Analysis of Multiobjective Optimization 2015 Tobias Brunsch
Heiko Röglin
+ PDF Chat Smoothed Analysis of the Successive Shortest Path Algorithm 2015 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
Clemens Rösner
+ PDF Chat Polynomial Kernels for Weighted Problems 2015 Michael Etscheid
Stefan Kratsch
Matthias Mnich
Heiko Röglin
+ Smoothed Analysis 2015 Heiko Röglin
+ Smoothed Analysis of the Successive Shortest Path Algorithm 2015 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
Clemens Rösner
+ Polynomial Kernels for Weighted Problems 2015 Michael Etscheid
Stefan Kratsch
Matthias Mnich
Heiko Röglin
+ Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering 2015 Carsten Fischer
Heiko Röglin
+ New Deterministic Algorithms for Solving Parity Games 2015 Matthias Mnich
Heiko Röglin
Clemens Rösner
+ Efficient Clustering with Limited Distance Information 2014 Konstantin Voevodski
Maria-Florina Balcan
Heiko Röglin
Shang‐Hua Teng
Yu Xia
+ Solving Totally Unimodular LPs with the Shadow Vertex Algorithm 2014 Tobias Brunsch
Anna Großwendt
Heiko Röglin
+ Worst-case and smoothed analysis of k-means clustering with Bregman divergences 2013 Bodo Manthey
Heiko Röglin
+ PDF Chat Smoothed performance guarantees for local search 2013 Tobias Brunsch
Heiko Röglin
Cyriel Rutten
Tjark Vredeveld
+ Finding Short Paths on Polytopes by the Shadow Vertex Algorithm 2013 Tobias Brunsch
Heiko Röglin
+ Smoothed Analysis of the Successive Shortest Path Algorithm 2013 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
+ PDF Chat Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching 2013 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
+ PDF Chat Finding Short Paths on Polytopes by the Shadow Vertex Algorithm 2013 Tobias Brunsch
Heiko Röglin
+ Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching 2013 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
+ Finding Short Paths on Polytopes by the Shadow Vertex Algorithm 2013 Tobias Brunsch
Heiko Röglin
+ Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching 2012 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
+ PDF Chat Improved smoothed analysis of multiobjective optimization 2012 Tobias Brunsch
Heiko Röglin
+ Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching 2012 Tobias Brunsch
Kamiel Cornelissen
Bodo Manthey
Heiko Röglin
+ Improved Smoothed Analysis of Multiobjective Optimization 2011 Tobias Brunsch
Heiko Röglin
+ Smoothed Performance Guarantees for Local Search 2011 Tobias Brunsch
Heiko Röglin
Cyriel Rutten
Tjark Vredeveld
+ Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function 2011 Konstantin Voevodski
Maria-Florina Balcan
Heiko Röglin
Shang‐Hua Teng
Yu Xia
+ PDF Chat Lower Bounds for the Smoothed Number of Pareto Optimal Solutions 2011 Tobias Brunsch
Heiko Röglin
+ PDF Chat Smoothed Performance Guarantees for Local Search 2011 Tobias Brunsch
Heiko Röglin
Cyriel Rutten
Tjark Vredeveld
+ Smoothed Performance Guarantees for Local Search 2011 Tobias Brunsch
Heiko Röglin
Cyriel Rutten
Tjark Vredeveld
+ Improved Smoothed Analysis of Multiobjective Optimization 2011 Tobias Brunsch
Heiko Röglin
+ Smoothed Analysis of Multiobjective Optimization 2009 Heiko Röglin
Shang‐Hua Teng
+ Improved smoothed analysis of the k-means method 2009 Bodo Manthey
Heiko Röglin
+ Improved Smoothed Analysis of the <i>k</i>-Means Method 2009 Bodo Manthey
Heiko Röglin
+ PDF Chat Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences 2009 Bodo Manthey
Heiko Röglin
+ k-Means has Polynomial Smoothed Complexity 2009 David Arthur
Bodo Manthey
Heiko Röglin
+ On the Convergence Time of the Best Response Dynamics in Player-specific Congestion Games 2008 Heiner Ackermann
Heiko Röglin
+ Approximate Equilibria in Games with Few Players 2008 Patrick Briest
Paul W. Goldberg
Heiko Röglin
+ Improved Smoothed Analysis of the k-Means Method 2008 Bodo Manthey
Heiko Röglin
Common Coauthors
Commonly Cited References
Action Title Year Authors # of times referenced
+ Smoothed analysis of algorithms 2004 Daniel A. Spielman
Shang‐Hua Teng
20
+ Smoothed analysis 2009 Daniel A. Spielman
Shang‐Hua Teng
11
+ Smoothed Analysis of Multiobjective Optimization 2009 Heiko Röglin
Shang‐Hua Teng
7
+ PDF Chat Improved smoothed analysis of multiobjective optimization 2012 Tobias Brunsch
Heiko Röglin
6
+ PDF Chat Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices 2006 Arvind Sankar
Daniel A. Spielman
Shang‐Hua Teng
5
+ Pareto optimal solutions for smoothed analysts 2011 Ankur Moitra
Ryan O’Donnell
4
+ PDF Chat Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method 2009 Roman Vershynin
4
+ PDF Chat Pareto Optimal Solutions for Smoothed Analysts 2012 Ankur Moitra
Ryan O’Donnell
4
+ Lower Bounds for the Average and Smoothed Number of Pareto Optima 2011 Navin Goyal
Luis Rademacher
3
+ PDF Chat Message Passing for Maximum Weight Independent Set 2009 Sujay Sanghavi
Devavrat Shah
Alan S. Willsky
3
+ PDF Chat Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems 2007 Ilias Diakonikolas
Mihalis Yannakakis
3
+ PDF Chat A rigorous analysis of the cavity equations for the minimum spanning tree 2008 Mohsen Bayati
Alfredo Braunstein
Riccardo Zecchina
3
+ PDF Chat Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality 2008 Mohsen Bayati
Devavrat Shah
Mayank Sharma
3
+ PDF Chat Parameterizing by the Number of Numbers 2011 Michael R. Fellows
Serge Gaspers
Frances Rosamond
3
+ PDF Chat On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility 2013 Stefan Kratsch
3
+ On simultaneous approximation in quadratic integer programming 1989 Frieda Granot
Jadranka Skorin‐Kapov
3
+ Random walks, totally unimodular matrices, and a randomised dual simplex algorithm 1994 Martin Dyer
Alan Frieze
3
+ PDF Chat On sub-determinants and the diameter of polyhedra 2012 Nicolas Bonifas
Marco Di Summa
Friedrich Eisenbrand
Nicolai Hähnle
Martin Niemeier
3
+ PDF Chat Smoothed analysis of termination of linear programming algorithms 2003 Daniel A. Spielman
Shang‐Hua Teng
2
+ PDF Chat Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes 2011 Endre Boros
Khaled Elbassioni
Mahmoud Fouz
Vladimir Gurvich
Kazuhisa Makino
Bodo Manthey
2
+ PDF Chat Probabilistic Analysis of the Simplex Method 1988 Karl Heinx Borgwardt
2
+ Coresets and approximate clustering for Bregman divergences 2009 Marcel R. Ackermann
Johannes Blömer
2
+ PDF Chat None 2014 Tobias Brunsch
Navin Goyal
Luis Rademacher
Heiko Roeglin
2
+ PDF Chat Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions 2011 Mohsen Bayati
Christian Borgs
Jennifer Chayes
Riccardo Zecchina
2
+ Improved smoothed analysis of the k-means method 2009 Bodo Manthey
Heiko Röglin
2
+ The hirsch conjecture is true for (0, 1)-polytopes 1989 Denis Naddef
2
+ PDF Chat Belief Propagation for Min-Cost Network Flow: Convergence and Correctness 2012 David Gamarnik
Devavrat Shah
Yehua Wei
2
+ None 2006 Tom Bohman
Alan Frieze
Ryan R. Martin
Miklós Ruszinkó
Clifford Smyth
2
+ PDF Chat Kernelization Lower Bounds by Cross-Composition 2014 Hans L. Bodlaender
Bart Jansen
Stefan Kratsch
2
+ PDF Chat Improved Smoothed Analysis of Multiobjective Optimization 2015 Tobias Brunsch
Heiko Röglin
2
+ PDF Chat Settling the complexity of computing two-player Nash equilibria 2009 Xi Chen
Xiaotie Deng
Shang‐Hua Teng
2
+ An application of simultaneous diophantine approximation in combinatorial optimization 1987 András Frank
Éva Tardos
2
+ Clustering with Bregman Divergences 2004 Arindam Banerjee
Srujana Merugu
Inderjit S. Dhillon
Joydeep Ghosh
2
+ Clustering for metric and non-metric distance measures 2008 Marcel R. Ackermann
Johannes Blömer
Christian Sohler
2
+ PDF Chat Reducing a Target Interval to a Few Exact Queries 2012 Jesper Nederlof
Erik Jan van Leeuwen
Ruben van der Zwaan
2
+ PDF Chat k-means requires exponentially many iterations even in the plane 2009 Andrea Vattani
2
+ PDF Chat Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem 2009 Justin Salez
Devavrat Shah
2
+ PDF Chat A counterexample to the Hirsch Conjecture 2012 Francisco Santos
2
+ Smoothed analysis of binary search trees 2007 Bodo Manthey
Rüdiger Reischuk
2
+ PDF Chat Output-sensitive complexity of multiobjective combinatorial optimization 2017 Fritz Bökler
Matthias Ehrgott
Christopher Morris
Petra Mutzel
2
+ PDF Chat Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation 2013 Dániel Marx
László A. Végh
2
+ PDF Chat A Spectral Approach to Analysing Belief Propagation for 3-Colouring 2009 Amin Coja‐Oghlan
Elchanan Mossel
Dan Vilenchik
2
+ PDF Chat A polynomial time primal network simplex algorithm for minimum cost flows 1997 James B. Orlin
2
+ A strongly polynomial minimum cost circulation algorithm 1985 Éva Tardos
1
+ The Steinitz constant of the plane. 1987 Wojciech Banaszczyk
1
+ PDF Chat An Improved Approximation for <i>k</i> -Median and Positive Correlation in Budgeted Optimization 2017 Jarosław Byrka
Thomas Pensyl
Bartosz Rybicki
Aravind Srinivasan
Khoa Trinh
1
+ Probability: Theory and Examples. 1992 Kathryn Prewitt
Richard Durrett
1
+ PDF Chat Smoothed performance guarantees for local search 2013 Tobias Brunsch
Heiko Röglin
Cyriel Rutten
Tjark Vredeveld
1
+ PDF Chat Approximation schemes for single machine scheduling with non-renewable resource constraints 2013 Péter Györgyi
Tamás Kis
1
+ Lower bounds for approximation by nonlinear manifolds 1968 Hugh E. Warren
1