APPROXNP

Approximation of NP-hard optimization problems

Coordinatore	KUNGLIGA TEKNISKA HOEGSKOLAN    more Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie.
Nazionalità Coordinatore	Sweden [SE]
Totale costo	2˙376˙000 €
EC contributo	2˙376˙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-2008-AdG
Funding Scheme	ERC-AG
Anno di inizio	2009
Periodo (anno-mese-giorno)	2009-01-01   -   2014-12-31

 Partecipanti

#	participant	country	role	EC contrib. [€]
1	KUNGLIGA TEKNISKA HOEGSKOLAN  Organization address address: Valhallavaegen 79 city: STOCKHOLM postcode: 10044 contact info Titolo: Ms. Nome: Harriett Cognome: Johansson Email: send email Telefono: +46 8 790 7899 Fax: +46 8 7900930	SE (STOCKHOLM)	hostInstitution	0.00
2	KUNGLIGA TEKNISKA HOEGSKOLAN  Organization address address: Valhallavaegen 79 city: STOCKHOLM postcode: 10044 contact info Titolo: Prof. Nome: Johan Cognome: Håstad Email: send email Telefono: +46 8 790 6289 Fax: +46 8 790 0930	SE (STOCKHOLM)	hostInstitution	0.00

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

The proposed project aims to create a center of excellence that aims at understanding the approximability of NP-hard optimization problems. In particular, for central problems like vertex cover, coloring of graphs, and various constraint satisfaction problems we want to study upper and lower bounds on how well they can be approximated in polynomial time. Many existing strong results are based on what is known as the Unique Games Conjecture (UGC) and a significant part of the project will be devoted to studying this conjecture. We expect that a major step needed to be taken in this process is to further develop the understanding of Boolean functions on the Boolean hypercube. We anticipate that the tools needed for this will come in the form of harmonic analysis which in its turn will rely on the corresponding results in the analysis of functions over the domain of real numbers.