BEYONDWORSTCASE

Algorithms beyond the Worst Case

Coordinatore	RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN    more 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

#	participant	country	role	EC contrib. [€]
1	RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN  Organization address address: REGINA PACIS WEG 3 city: BONN postcode: 53113 contact info Titolo: Ms. Nome: Daniela Cognome: Hasenpusch Email: send email Telefono: +49 228 737274 Fax: +49 228 736479	DE (BONN)	hostInstitution	1˙235˙820.00
2	RHEINISCHE FRIEDRICH-WILHELMS-UNIVERSITAT BONN  Organization address address: REGINA PACIS WEG 3 city: BONN postcode: 53113 contact info Titolo: Prof. Nome: Heiko Cognome: Roglin Email: send email Telefono: +49 228 73 4326	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.'