OPTAPPROX

Strong Convex Relaxations with Optimal Approximation Guarantees

 Coordinatore ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE 

Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie.

 Nazionalità Coordinatore Switzerland [CH]
 Totale costo 1˙451˙052 €
 EC contributo 1˙451˙052 €
 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-2013-StG
 Funding Scheme ERC-SG
 Anno di inizio 2014
 Periodo (anno-mese-giorno) 2014-01-01   -   2018-12-31

 Partecipanti

# participant  country  role  EC contrib. [€] 
1    ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE

 Organization address address: BATIMENT CE 3316 STATION 1
city: LAUSANNE
postcode: 1015

contact info
Titolo: Dr.
Nome: Caroline
Cognome: Vandevyver
Email: send email
Telefono: +41 21 693 35 73
Fax: +41 21 693 55 83

CH (LAUSANNE) hostInstitution 1˙451˙052.00
2    ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE

 Organization address address: BATIMENT CE 3316 STATION 1
city: LAUSANNE
postcode: 1015

contact info
Titolo: Prof.
Nome: Ola Nils Anders
Cognome: Svensson
Email: send email
Telefono: +41 21 693 1204
Fax: +41 21 693 7510

CH (LAUSANNE) hostInstitution 1˙451˙052.00

Mappa

Leaflet | Map data © OpenStreetMap contributors, CC-BY-SA, Imagery © Mapbox

 Word cloud

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

power    prove    algorithms    relaxations    fundamental    science    computer    theoretical    approximation    convex    conjecture    directions    optimization   

 Obiettivo del progetto (Objective)

'One of the most exciting areas of theoretical computer science is to understand the approximability of fundamental optimization problems. A prominent example is the traveling salesman problem, for which a long-standing conjecture states that a certain algorithm gives a better guarantee than current methods can prove. The resolution of this conjecture and of many other fundamental problems is intimately related to an increased understanding of strong convex relaxations.

Although these problems have resisted numerous attempts, recent breakthrough results, in which the PI has played a central role, indicate new research directions with the potential to resolve some of our most exciting open questions. We propose three research directions to revolutionize our understanding of these problems and more generally of the use of convex relaxations in approximation algorithms:

(I) develop new approaches to analyze and harness the power of existing convex relaxations;

(II) understand the power of automatically generated relaxations; and

(III) prove the optimality of algorithms based on convex relaxations.

The proposed research lies in the frontier of approximation algorithms and optimization with connections to major problems in complexity theory, such as the unique games conjecture. Any progress will be a significant contribution to theoretical computer science and mathematical optimization.'

Altri progetti dello stesso programma (FP7-IDEAS-ERC)

SPECMATE (2012)

Specification Mining and Testing

Read More  

SEDMORPH (2012)

"The origins of galaxy bimodality: Linking mergers, starbursts and feedback in observations and simulations"

Read More  

STEMCELLMARK (2009)

LGR receptors mark adult stem cells in multiple mammalian tissues

Read More