Hola,
¿eres nuevo aquí?

Regístrate gratis y conecta tu empresa con financiación pública, partners y proyectos.

Tengo cuenta

Regístrate

Ver video

OptApprox

Financiado

Cerrado

Strong Convex Relaxations with Optimal Approximation Guarantees

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... ver más

31/12/2018

EPFL

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Fecha límite participación Sin fecha límite de participación.

Financiación concedida El organismo FP7 notifico la concesión del proyecto el día 2018-12-31 No tenemos la información de la convocatoria

0% 100% 100%

Información adicional privada

No hay información privada compartida para este proyecto. Habla con el coordinador.

1 Participantes

EPFL

0.00€ | Lider

Conecta tu I+D

¿Tienes un proyecto y buscas un partner? Gracias a nuestro motor inteligente podemos recomendarte los mejores socios y ponerte en contacto con ellos. Te lo explicamos en este video

Proyectos interesantes

PowAlgDO Power of Algorithms in Discrete Optimisation 1M€ Cerrado

AUTAR A Unified Theory of Algorithmic Relaxations 2M€ Cerrado

OPT-GEOM-RS Optimization Problems on Geometric Range Spaces 100K€ Cerrado

ALGOCom Novel Algorithmic Techniques through the Lens of Combinatori... 1M€ Cerrado

CRACKNP Finding Cracks in the Wall of NP completeness 1M€ Cerrado

PACKENUM PArameterized Complexity and Kernelization for ENUMeration 141K€ Cerrado

Líder del proyecto

ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Presupuesto del proyecto 1M€

Fecha límite de participación Sin fecha límite de participación.

Descripción del proyecto 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.

Conecta tu I+D

Entra hoy

¿Olvidé mi contraseña?

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores