http://www.dagstuhl.de/14372

September 7 – 12 , 2014, Dagstuhl Seminar 14372

Analysis of Algorithms Beyond the Worst Case

Organizers

Maria-Florina Balcan (Carnegie Mellon University, US)
Bodo Manthey (University of Twente, NL)
Heiko Röglin (Universität Bonn, DE)
Tim Roughgarden (Stanford University, US)


1 / 2 >

For support, please contact

Christina Schwarz for administrative matters

Marc Herbstritt for scientific matters

Documents

List of Participants
Shared Documents

Motivation

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. For example, worst-case analysis suggests that the simplex method is an exponential-time algorithm for linear programming, while in fact it runs in near-linear time on almost all inputs of interest. This is due to the fact that worst-case inputs are often rather contrived and occur hardly ever in practical applications. It led to the situation that for many problems the classical theory is not able to classify algorithms meaningfully according to their performance.

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 will discuss various recent theoretical models and results that go beyond worst-case analysis. These models can be divided into two main categories: Either they assume some randomness in the input (for instance, probabilistic and smoothed analysis or semirandom input models). Or they consider only inputs that satisfy certain deterministic properties that mitigate the worst case (for instance, planted and stable solutions or fixed-parameter tractability).

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

Classification

  • Data Structures / Algorithms / Complexity
  • Optimization / Scheduling

Keywords

  • Analysis of algorithms
  • Probabilistic analysis
  • Smoothed analysis
  • Clustering
  • Realistic input models
  • Robustness

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.