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

TOTAL

Financiado

Cerrado

Technology transfer between modern algorithmic paradigms

The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by... ver más

30/09/2021

UNIWARSAW

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

UNIWERSYTET WARSZAWSKI 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.

Ver 2 Participantes

Financiación concedida El organismo H2020 notifico la concesión del proyecto el día 2021-09-30

ERC-StG-2015: ERC Starting Grant

I+D

Cerrada hace 9 años

0% 100% 100%

Información adicional privada

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

2 Participantes

UNIWARSAW

1.42M€ | Lider

COMPAÑIA MATASO MATADERO DE...

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

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

SYSTEMATICGRAPH Systematic mapping of the complexity landscape of hard algor... 2M€ Cerrado

PARAPATH Parameterized Complexity Through the Lens of Path Problems 1M€ Cerrado

PARAMTIGHT Parameterized complexity and the search for tight complexity... 1M€ Cerrado

PARAPPROX Parameterized Approximation 2M€ Cerrado

PACKENUM PArameterized Complexity and Kernelization for ENUMeration 141K€ Cerrado

Duración del proyecto: 66 meses Fecha Inicio: 2016-03-02
Fecha Fin: 2021-09-30

Líder del proyecto

UNIWERSYTET WARSZAWSKI 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 The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by now developed, they have grown mostly on their own. In our opinion the two fields have critical mass allowing for synergy effects to appear when using techniques from one area to obtain results in the other, which is the main theme of the project. Furthermore, practical effectiveness of randomized local search heuristics is a not yet understood phenomenon. We believe that substantial increase of our understanding of superpolynomial running times in recent years should allow for rigorous proofs of parameterized and approximation results obtained by those methods. Based on our experience with parameterized complexity and approximation algorithms we propose three research directions with potential of solving major long-standing open problems in both areas with the following objectives. (a) Transfer from Approximation to FPT: use the PCP theorem to prove lower bounds for exact parameterized algorithms under the Exponential Time Hypothesis and take advantage of extended formulations in FPT branching algorithms. (b) Transfer from FPT to Approximation: utilize parameterized algorithms tools in local-search-based approximation algorithms and explore the potential of proving new inapproximability results based on the Exponential Time Hypothesis. (c) Rigorous Analysis of Practical Heuristics: unravel the practical effectiveness of randomized local search heuristics by proving their parameterized and approximation properties, when given subexponential or even moderately exponential running time. Our objectives lie in the frontier of fixed parameter tractability and approximation areas. Complete resolution of our goals would dramatically change our understanding of both areas, with further consequences in other disciplines within computer science.

Conecta tu I+D

Entra hoy

¿Olvidé mi contraseña?

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores