- Coordinator
- Syddansk Universitet, Denmark
- Runs
- 1 January 2026 to 31 December 2030
- Status
- Running
- EU funding
- €1.5m
- Total cost
- €1.5m
- Partners
- 1 organisations in 1 countries
- Type
- European Research Council grant
- Grant agreement
- 101220563
What the project is doing
In the project's own words, from its summary on CORDIS.
Polyhedral techniques allow the powerhouse of linear programming to be used for the discrete problems in combinatorial optimization. Their impact on commercial solvers, the theory of classical algorithms, as well as approximation algorithms, is well established. Nevertheless, these techniques play only a marginal role in mainstream research on parameterized algorithms. Recent advances, many of which are due to the PI, are showing potential for a revolutionary synergy between parameterized algorithms and polyhedral techniques.
This project aims to unlock the full power of this synergy and use it to address several pressing open questions in combinatorial optimization. The work plan consists of three complementary directions:I. Exploring new frontiers for polyhedral techniques in parameterized algorithms, in particular, the novel usage of proximity bounds to obtain FPT algorithms. We will specifically investigate the open question of whether bin packing in the number of item sizes is in FPT.II.
Closing notorious loose ends in existing research lines, in particular, the lack of polyhedral understanding of algebraic methods in matroid problems. III. Embracing parameterization to strengthen polyhedral techniques in approximation algorithms. Specifically, we will investigate an innovative technique crucial for understanding the approximability of scheduling on unrelated parallel machines, max-min fair allocation, and directed Steiner tree.
The topics of the project are relevant for a broad spectrum of researchers from both parameterized algorithms and approximation algorithms and have the potential to bring these fields much closer together.
Topics
Who is involved
| Organisation | City | Country | Role |
|---|---|---|---|
| Syddansk Universitet | Odense M | Denmark | Coordinator |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI