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 from 02/20 to 11/21

Alejandro Cassis: PhD student since 06/20

Karol Węgrzycki: Postdoc since 10/20

Evangelos Kipouridis: Postdoc since 09/22


Project Publications - Conferences


[32]

"Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution"

Karl Bringmann, Alejandro Cassis

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

[31]

"Improved Sublinear-Time Edit Distance for Preprocessed Strings"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

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

[30]

"A Structural Investigation of the Approximability of Polynomial-Time Problems"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

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

[29]

"Tight Fine-Grained Bounds for Direct Access on Join Queries"

Karl Bringmann, Nofar Carmeli, Stefan Mengel

PODS'22: Proc. of the 41st ACM Symposium on Principles of Database Systems

[28]

"Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves"

Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser

SoCG'22: Proc. of the 38th International Symposium on Computational Geometry

[27]

"Towards sub-quadratic diameter computation in geometric intersection graphs"

Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian

SoCG'22: Proc. of the 38th International Symposium on Computational Geometry

[26]

"Isolation Schemes for Problems on Decomposable Graphs"

Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, Karol Wegrzycki

STACS'22: Proc. of the 39th International Symposium on Theoretical Aspects of Computer Science

[25]

"Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond"

Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[24]

"Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[23]

"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[22]

"Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance"

Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[21]

"Fine-Grained Completeness for Optimization in P"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

APPROX-RANDOM'21: Proc. of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems

[20]

"Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry"

Karl Bringmann

CiE'21: Proc. of the 17th Conference on Computability in Europe

[19]

"A Gap-ETH-Tight Approximation Scheme for Euclidean TSP"

Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Wegrzycki

FOCS'21: Proc. of the 62nd Annual IEEE Symposium on Foundations of Computer Science

[18]

"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

[17]

"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

[16]

"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

[15]

"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

[14]

"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.

[13]

"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

[12]

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

Jesper Nederlof, Karol Wegrzycki

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

[11]

"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

[10]

"A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics"

Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki

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

[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


Project Publications - Journals


[5]

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

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

Algorithmica, 2022

[4]

"Scheduling Lower Bounds via AND Subset Sum"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

Journal of Computer and System Sciences, 2022

[3]

"SETH-based Lower Bounds for Subset Sum and Bicriteria Path"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

ACM Transactions on Algorithms, 2022

Special issue of SODA'19

[2]

"Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance"

Karl Bringmann, Marvin Künnemann, André Nusser

Journal of Computational Geometry, 2021

[1]

"Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm"

Karl Bringmann, Marvin Künnemann, André Nusser

ACM Transactions on Algorithms, 2021