Heiko Röglin

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Bicriteria Aggregation of Polygons via Graph Cuts.

[BibT_eX]

[DOI]

Proceedings of the 11th International Conference on Geographic Information Science, 2021

2020

Preface: 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2017).

[BibT_eX]

[DOI]

Discret. Appl. Math., 2020

Smoothed Analysis of Pareto Curves in Multiobjective Optimization.

[BibT_eX]

[DOI]

CoRR, 2020

Noisy, Greedy and Not so Greedy k-Means++.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Smoothed Analysis of Pareto Curves in Multiobjective Optimization.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Analysis of Ward's Method.

[BibT_eX]

[DOI]

Anna Großwendt

Melanie Schmidt

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

The Alternating Stock Size Problem and the Gasoline Puzzle.

[BibT_eX]

[DOI]

Alantha Newman

Johanna Seif

ACM Trans. Algorithms, 2018

New deterministic algorithms for solving parity games.

[BibT_eX]

[DOI]

Matthias Mnich

Clemens Rösner

Discret. Optim., 2018

Probabilistic Analysis of Online (Class-Constrained) Bin Packing and Bin Covering.

[BibT_eX]

[DOI]

Carsten Fischer

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017

Smoothed Analysis of Local Search for the Maximum-Cut Problem.

[BibT_eX]

[DOI]

Michael Etscheid

ACM Trans. Algorithms, 2017

Polynomial kernels for weighted problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Improved Analysis of Complete-Linkage Clustering.

[BibT_eX]

[DOI]

Anna Großwendt

Algorithmica, 2017

The Smoothed Number of Pareto-Optimal Solutions in Non-integer Bicriteria Optimization.

[BibT_eX]

[DOI]

Clemens Rösner

Proceedings of the Theory and Applications of Models of Computation, 2017

2016

Smoothed Analysis.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Smoothed Analysis of the 2-Opt Algorithm for the General TSP.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Bounds for the Convergence Time of Local Search in Scheduling Problems.

[BibT_eX]

[DOI]

Michael Etscheid

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering.

[BibT_eX]

[DOI]

Carsten Fischer

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

2015

Smoothed Analysis of the Successive Shortest Path Algorithm.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Improved Smoothed Analysis of Multiobjective Optimization.

[BibT_eX]

[DOI]

J. ACM, 2015

Internet routing between autonomous systems: Fast algorithms for path trading.

[BibT_eX]

[DOI]

André Berger

Ruben van der Zwaan

Discret. Appl. Math., 2015

Solving Totally Unimodular LPs with the Shadow Vertex Algorithm.

[BibT_eX]

[DOI]

Anna Großwendt

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem.

[BibT_eX]

[DOI]

Michael Etscheid

Proceedings of the Algorithms - ESA 2015, 2015

2014

Lower Bounds for the Average and Smoothed Number of Pareto-Optima.

[BibT_eX]

[DOI]

Theory Comput., 2014

Smoothed performance guarantees for local search.

[BibT_eX]

[DOI]

Math. Program., 2014

Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

2013

Economical Caching.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

A bad instance for k-means++.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.

[BibT_eX]

[DOI]

J. Comput. Geom., 2013

Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2013

Finding Short Paths on Polytopes by the Shadow Vertex Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Smoothed analysis of the successive shortest path algorithm.

[BibT_eX]

Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012

Theoretical analysis of two ACO approaches for the traveling salesman problem.

[BibT_eX]

[DOI]

Swarm Intell., 2012

Computing approximate Nash equilibria in network congestion games.

[BibT_eX]

[DOI]

Andreas Emil Feldmann

Networks, 2012

Active Clustering of Biological Sequences.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2012

2011

Competitive routing over time.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Uncoordinated Two-Sided Matching Markets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Smoothed Analysis of the k-Means Method.

[BibT_eX]

[DOI]

David Arthur

J. ACM, 2011

Smoothed Analysis: Analysis of Algorithms Beyond Worst Case.

[BibT_eX]

[DOI]

it Inf. Technol., 2011

Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function

[BibT_eX]

[DOI]

CoRR, 2011

Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results.

[BibT_eX]

[DOI]

André Berger

Ruben van der Zwaan

Proceedings of the Experimental Algorithms - 10th International Symposium, 2011

Lower Bounds for the Smoothed Number of Pareto Optimal Solutions.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2011

Min-sum Clustering of Protein Sequences with Limited Distance Information.

[BibT_eX]

[DOI]

Proceedings of the Similarity-Based Pattern Recognition - First International Workshop, 2011

2010

The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers.

[BibT_eX]

[DOI]

Patrick Briest

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Efficient Clustering with Limited Distance Information.

[BibT_eX]

[DOI]

Proceedings of the UAI 2010, 2010

Analysis of Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice [outcome of a Dagstuhl Seminar], 2010

Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

Proceedings of the Swarm Intelligence - 7th International Conference, 2010

2009

Pure Nash equilibria in player-specific and weighted congestion games.

[BibT_eX]

[DOI]

Heiner Ackermann

Theor. Comput. Sci., 2009

Evaluation of online strategies for reordering buffers.

[BibT_eX]

[DOI]

Matthias Westermann

ACM J. Exp. Algorithmics, 2009

Improved smoothed analysis of the <i>k</i>-means method.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Worst-Case and Smoothed Analysis of <i>k</i>-Means Clustering with Bregman Divergences.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Smoothed Analysis of Multiobjective Optimization.

[BibT_eX]

[DOI]

Shang-Hua Teng

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

k-Means Has Polynomial Smoothed Complexity.

[BibT_eX]

[DOI]

David Arthur

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Agnostic Clustering.

[BibT_eX]

[DOI]

Maria-Florina Balcan

Shang-Hua Teng

Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008

A Unified Approach to Congestion Games and Two-Sided Markets.

[BibT_eX]

[DOI]

Internet Math., 2008

Improved Smoothed Analysis of the k-Means Method

[BibT_eX]

[DOI]

CoRR, 2008

On the Convergence Time of the Best Response Dynamics in Player-specific Congestion Games

[BibT_eX]

[DOI]

Heiner Ackermann

CoRR, 2008

Approximate Equilibria in Games with Few Players

[BibT_eX]

[DOI]

Patrick Briest

Paul W. Goldberg

CoRR, 2008

2007

Decision-making based on approximate and smoothed Pareto curves.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Smoothed analysis of integer programming.

[BibT_eX]

[DOI]

Math. Program., 2007

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization.

[BibT_eX]

[DOI]

René Beier

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On the Impact of Combinatorial Structure on Congestion Games.

[BibT_eX]

[DOI]

Heiner Ackermann