ALGOCom
Financiado
Novel Algorithmic Techniques through the Lens of Combinatorics
Real-world optimization problems pose major challenges to algorithmic research. For instance, (i) many important problems are believed to be intractable (i.e. NP-hard) and (ii) with the growth of data size, modern applications of...
Real-world optimization problems pose major challenges to algorithmic research. For instance, (i) many important problems are believed to be intractable (i.e. NP-hard) and (ii) with the growth of data size, modern applications often require a decision making under {\em incomplete and dynamically changing input data}. After several decades of research, central problems in these domains have remained poorly understood (e.g. Is there an asymptotically most efficient binary search trees?) Existing algorithmic techniques either reach their limitation or are inherently tailored to special cases.
This project attempts to untangle this gap in the state of the art and seeks new interplay across multiple areas of algorithms, such as approximation algorithms, online algorithms, fixed-parameter tractable (FPT) algorithms, exponential time algorithms, and data structures. We propose new directions from the {\em structural perspectives} that connect the aforementioned algorithmic problems to basic questions in combinatorics.
Our approaches fall into one of the three broad schemes: (i) new structural theory, (ii) intermediate problems, and (iii) transfer of techniques. These directions partially build on the PI's successes in resolving more than ten classical problems in this context.
Resolving the proposed problems will likely revolutionize our understanding about algorithms and data structures and potentially unify techniques in multiple algorithmic regimes. Any progress is, in fact, already a significant contribution to the algorithms community. We suggest concrete intermediate goals that are of independent interest and have lower risks, so they are suitable for Ph.D students.
ver más
Duración del proyecto: 76 meses
Fecha Inicio: 2017-09-01
Fecha Fin: 2024-01-31
Fecha Fin: 2024-01-31
Línea de financiación: concedida
El organismo H2020 notifico la concesión del proyecto el día 2024-01-31
Línea de financiación objetivo
El proyecto se financió a través de la siguiente ayuda:
ERC-2017-STG:
ERC Starting Grant
Cerrada
hace 8 años
Presupuesto
El presupuesto total del proyecto asciende a
1M€
Líder del proyecto
AALTO KORKEAKOULUSAATIO SR
No se ha especificado una descripción o un objeto social para esta compañía.
Perfil tecnológico
TRL
4-5
Perfil tecnológico
TRL
4-5
602.40K€ |
Participante