PARAMTIGHT
Parameterized complexity and the search for tight complexity results
| Coordinatore | MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | Hungary [HU] |
| Totale costo | 1˙150˙000 € |
| EC contributo | 1˙150˙000 € |
| 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-2011-StG_20101014 |
| Funding Scheme | ERC-SG |
| Anno di inizio | 2012 |
| Periodo (anno-mese-giorno) | 2012-01-01 - 2016-12-31 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET
Organization address
address: Kende utca 13-17 contact info |
HU (BUDAPEST) | hostInstitution | 1˙150˙000.00 |
| 2 |
MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET
Organization address
address: Kende utca 13-17 contact info |
HU (BUDAPEST) | hostInstitution | 1˙150˙000.00 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'The joint goal of theoretical research in algorithms and computational complexity is to discover all the relevant algorithmic techniques in a problem domain and prove the optimality of these techniques. We propose that the search for such tight results should be done by a combined exploration of the dimensions running time, quality of solution, and generality. Furthermore, the theory of parameterized complexity provides a framework for this exploration.
Parameterized complexity is a theory whose goal is to produce efficient algorithms for hard combinatorial problems using a multi-dimensional analysis of the running time. Instead of expressing the running time as a function of the input size only (as it is done in classical complexity theory), parameterized complexity tries to find algorithms whose running time is polynomial in the input size, but exponential in one or more well-defined parameters of the input instance.
The first objective of the project is to go beyond the state of the art in the complexity and algorithmic aspects of parameterized complexity in order to turn it into a theory producing tight optimality results. With such theory at hand, we can start the exploration of other dimensions and obtain tight optimality results in a larger context. Our is goal is being able to prove in a wide range of settings that we understand all the algorithmic ideas and their optimality.'