BEYONDWORSTCASE
Algorithms beyond the Worst Case
| Coordinatore | RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | Germany [DE] |
| Totale costo | 1˙235˙820 € |
| EC contributo | 1˙235˙820 € |
| Programma | FP7-IDEAS-ERC
Specific programme: "Ideas" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013) |
| Code Call | ERC-2012-StG_20111012 |
| Funding Scheme | ERC-SG |
| Anno di inizio | 2012 |
| Periodo (anno-mese-giorno) | 2012-10-01 - 2017-09-30 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN
Organization address
address: REGINA PACIS WEG 3 contact info |
DE (BONN) | hostInstitution | 1˙235˙820.00 |
| 2 |
RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN
Organization address
address: REGINA PACIS WEG 3 contact info |
DE (BONN) | hostInstitution | 1˙235˙820.00 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'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. This project will play a major role in this paradigm shift by developing and exploring novel theoretical approaches (e.g. smoothed analysis) to reconcile theory and practice. A more realistic theory will have a profound impact on the design and analysis of algorithms in the future, and the insights gained in this project will lead to algorithmic tools for large-scale optimization problems that improve on existing ad hoc methods. We will not only work theoretically but also test the applicability of our theoretical considerations in experimental studies.'