Algorithms beyond the Worst Case
Supported by an ERC Starting Grant from October 2012 until September 2017.
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.
- Heiko Röglin (Principal Investigator)
- Michael Etscheid (PhD student)
- Carsten Fischer (PhD student)
- Matthias Mnich (Postdoc)
- Melanie Schmidt (Postdoc)
- Andreas Tönnis (Postdoc)
Analysis of Ward's Method
To appear in Proc. of the 30th SODA (San Diego, USA), 2019.
Probabilistic Analysis of (Class-constrained) Bin Packing and Bin Covering
In Proc. of the 13th LATIN (Buenos Aires, Argentina), pp. 461--474, 2018.
The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization
In Proc. of the 14th TAMC (Bern, Switzerland), pp. 543-555, 2017.
Bounds for the Convergence Time of Local Search in Scheduling Problems
In Proc. of the 12th WINE (Montreal, Canada), pp. 339-353, 2016.
The Alternating Stock Size Problem and the Gasoline Puzzle
In Proc. of the 24th ESA (Aarhus, Denmark), pp. 71:1-71:16, 2016.
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 469-482, 2016.
New Deterministic Algorithms for Solving Parity Games
In Proc. of the 12th LATIN (Ensenada, Mexico), pp. 634-645, 2016.
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.
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
In Proc. of the 23rd ESA (Patras, Greece), pp. 509-520, 2015.
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.
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
In Proc. of the 32nd STACS (Munich, Germany), pp. 171-183, 2015.
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.
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.
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
In Proc. of the 40th ICALP (Riga, Latvia), pp. 279-290, 2013.
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.
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.