ERC Starting Grant · 2019
Technology Transfer between Integer Programming and Efficient Algorithms
This project aims to resolve challenging integer programming problems in exact and approximate settings, with a focus on Knapsack-type problems (such as Subset Sum, Partition, and Knapsack). To this end, we will develop a unified approach of algorithm design as a combination of algorithmic tools, structural theory, and conditional lower bounds. Specific tasks include: - utilizing recent advances in efficient algorithms, since although Knapsack-type algorithms are NP-hard their main challenges ask for polynomial improvements in running time, - leveraging structural results from additive combinatorics for the design of algorithms for problems of additive nature, such as Knapsack-type…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.