License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.4.9.30
URN: urn:nbn:de:0030-drops-48829
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4882/
Go back to Dagstuhl Reports

Balcan, Marina-Florina ; Manthey, Bodo ; Röglin, Heiko ; Roughgarden, Tim
Weitere Beteiligte (Hrsg. etc.): Maria-Florina Balcan and Bodo Manthey and Heiko Röglin and Tim Roughgarden

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

pdf-format:
dagrep_v004_i009_p30_s14372.pdf (1 MB)

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.

BibTeX - Entry

@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}
}

Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning
Collection: Dagstuhl Reports, Volume 4, Issue 9
Issue Date: 2015
Date of publication: 08.01.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI