Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 14372 "Analysis of Algorithms Beyond the Worst Case".

The theory of algorithms has traditionally focused on worst-case analysis. This focus has led to both a deep theory and many beautiful and useful algorithms. However, there are a number of important problems and algorithms for which worst-case analysis does not provide useful or empirically accurate results. This is due to the fact that worst-case inputs are often rather contrived and occur hardly ever in practical applications. Only in recent years a paradigm shift towards a more realistic and robust algorithmic theory has been initiated. The development of a more realistic theory hinges on finding models that measure the performance of an algorithm not only by its worst-case behavior but rather by its behavior on "typical" inputs. In this seminar, we discussed various recent theoretical models and results that go beyond worst-case analysis.

The seminar helped to consolidate the research and to foster collaborations among the researchers working in the different branches of analysis of algorithms beyond the worst case.

@Article{balcan_et_al:DR:2015:4882,
  author =	{Marina-Florina Balcan and Bodo Manthey and Heiko R{\"o}glin and Tim Roughgarden},
  title =	{{Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)}},
  pages =	{30--49},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{9},
  editor =	{Maria-Florina Balcan and Bodo Manthey and Heiko R{\"o}glin and Tim Roughgarden},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4882},
  URN =		{urn:nbn:de:0030-drops-48829},
  doi =		{10.4230/DagRep.4.9.30},
  annote =	{Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning}
}