PARAMTIGHT

Parameterized complexity and the search for tight complexity results

Coordinatore	MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET    more 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

#	participant	country	role	EC contrib. [€]
1	MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET  Organization address address: Kende utca 13-17 city: BUDAPEST postcode: 1111 contact info Titolo: Dr. Nome: Andras Cognome: Benczur Email: send email Telefono: +36 1 279 6172 Fax: +36 1 209 5269	HU (BUDAPEST)	hostInstitution	1˙150˙000.00
2	MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATO INTEZET  Organization address address: Kende utca 13-17 city: BUDAPEST postcode: 1111 contact info Titolo: Dr. Nome: Dániel Cognome: Marx Email: send email Telefono: 3612796172 Fax: 3612095269	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.'