Heiko Röglin
ERC Logo

Algorithms beyond the Worst Case

Supported by an ERC Starting Grant from October 2012 until September 2017.

FP7 Logo

Project

For many optimization problems that arise in logistics, information retrieval, and other contexts the classical theory of algorithms has lost its grip on reality because it is based on a pessimistic worst-case perspective, in which the performance of an algorithm is solely measured by its behavior on the worst possible input. This does not take into consideration that worst-case inputs are often rather contrived and occur only rarely in practical applications. It led to the situation that for many problems the classical theory is not able to differentiate meaningfully between different algorithms. Even worse, for some important problems it recommends algorithms that perform badly in practice over algorithms that work well in practice only because the artificial worst-case performance of the latter ones is bad.

We will study classic optimization problems (traveling salesperson problem, linear programming, etc.) as well as problems coming from machine learning and information retrieval. All these problems have in common that the practically most successful algorithms have a devastating worst-case performance even though they clearly outperform the theoretically best algorithms.

Only in recent years a paradigm shift towards a more realistic and robust algorithmic theory has been initiated. In this project we will develop and explore novel theoretical approaches to reconcile theory and practice. We will, in particular, analyze algorithms and optimization problems in the framework of smoothed analysis. In this model, inputs are generated in two steps: first, an adversary chooses an arbitrary instance, and then this instance is slightly perturbed at random. The smoothed performance of an algorithm is defined to be the worst expected performance the adversary can achieve. This model can be viewed as a less pessimistic worst-case analysis, in which the randomness rules out pathological worst-case instances that are rarely observed in practice but dominate the worst-case analysis.


Team Members


Publications

[16]
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
[15]
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
[14]
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.
WWW   PDF
[13]
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
[12]
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.
WWW   PDF
[11]
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
[10]
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.
WWW   PDF
[9]
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 to appear in special issue of Algorithmica.
WWW   PDF
[8]
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
[7]
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.
Journal of Computer and System Sciences, 84:1-10, 2017.
WWW   PDF
[6]
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
[5]
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.
ACM Transactions on Algorithms, 13(2), 2017.
WWW   PDF
[4]
Michael Etscheid
Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds
In Proc. of the 24th ISAAC (Hong Kong), pp. 207-217, 2013.
Discrete Applied Mathematics, 2014.
WWW
[3]
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
[2]
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.
Journal of Graph Algorithms and Applications, 17(6):647-670, 2013.
WWW   PDF
[1]
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.
SIAM Journal on Computing, 44(6):1798-1819, 2015.
WWW   PDF