Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Karl Bringmann: ERC Starting Grant TIPEA

Logo ERC Logo EU

Project "Technology Transfer between Integer Programming and Efficient Algorithms" (TIPEA)

TIPEA is a project in theoretical computer science that seeks a deeper understanding of fundamental optimization problems such as Subset Sum, Knapsack, and more generally Integer Programming. These problems arise in everyday situations such as finding out which lectures can be attended without collision, as well as in less commonplace areas such as post-quantum cryptography, where the hardness of Subset Sum is used to design software that is secure against quantum computers. Since modern solvers can handle industrial instances with up to millions of variables despite the problem being NP-hard, Integer Programming has become a vital tool for industry. The goal of this project is to utilize recent advances in theoretical computer science to design faster, and in many cases best-possible algorithms for these fundamental optimization problems, in order to lay the foundations for next-generation industrial solvers. To this end, we develop an algorithm design approach consisting of (1) modern algorithmic techniques such as dynamic or sublinear-time algorithms to design faster subroutines, (2) mathematical structure theory such as additive combinatorics to gain problem insights, and (3) the recently developed fine-grained complexity theory to establish that our algorithms are best-possible. We apply this approach to open problems on exact, parameterized, and approximation algorithms for Subset Sum, Knapsack, and Integer Programming, as well as various combinatorial problems beyond optimization. Conversely, we also want to utilize the insights of practical integer programming solvers to obtain highly-efficient implementations for problems from different domains.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 850979). The project is running from 11/2019-10/2024.


Project Members


Karl Bringmann: Principal Investigator

Nick Fischer: PhD student since 01/20

Vasileios Nakos: Postdoc since 02/20

Alejandro Cassis: PhD student since 06/20

Karol Węgrzycki: Postdoc since 10/20


Project Publications


[17]

"Fast n-fold Boolean Convolution via Additive Combinatorics"

Karl Bringmann, Vasileios Nakos

ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming

[16]

"Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal"

Karl Bringmann, Jasper Slusallek

ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming

[15]

"Knapsack and Subset Sum with Small Items"

Adam Polak, Lars Rohwedder, Karol Węgrzycki

ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming

[14]

"On the Approximability of Multistage Min-Sum Set Cover"

Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis

ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming

[13]

"A Linear-Time n0.4-Approximation for Longest Common Subsequence"

Karl Bringmann, Vincent Cohen-Addad*, Debarati Das

ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming

*Vincent Cohen-Addad is author of the extended Arxiv version, but not of the ICALP proceedings version.

[12]

"Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing

[11]

"Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors"

Jesper Nederlof, Karol Węgrzycki

STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing

[10]

"Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation"

Karl Bringmann, André Nusser

SoCG'21: Proc. of the 37rd International Symposium on Computational Geometry

Invited to JoCG special issue

[9]

"A Fine-Grained Perspective on Approximating Subset Sum and Partition"

Karl Bringmann, Vasileios Nakos

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[8]

"On Near-Linear-Time Algorithms for Dense Subset Sum"

Karl Bringmann, Philip Wellnitz

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[7]

"Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time"

Mahdi Cheraghchi, Vasileios Nakos

FOCS'20: Proc. of the 61st Annual IEEE Symposium on Foundations of Computer Science

[6]

"Fast and Simple Modular Subset Sum"

Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu

SOSA@SODA'21: Proc. of the 4th SIAM Symposium on Simplicity in Algorithms

[5]

"Impossibility Results for Grammar-Compressed Linear Algebra"

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

NeurIPS'20: Proc. of the 34th Annual Conference on Neural Information Processing Systems

[4]

"When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation"

Karl Bringmann, Marvin Künnemann, André Nusser

ESA'20: Proc. of the 28th Annual European Symposium on Algorithms

[3]

"Scheduling Lower Bounds via AND Subset Sum"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

ICALP'20: Proc. of the 47th International Colloquium on Automata, Languages, and Programming

[2]

"Faster Minimization of Tardy Processing Time on a Single Machine"

Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz

ICALP'20: Proc. of the 47th International Colloquium on Automata, Languages, and Programming

[1]

"Top-k-Convolution and the Quest for Near-linear Output-sensitive Subset Sum"

Karl Bringmann, Vasileios Nakos

STOC'20: Proc. of the 52nd ACM Symposium on the Theory of Computing