max planck institut
informatik
informatik
TIPEA was a project in theoretical computer science seeking a deeper understanding of fundamental optimization problems such as Subset Sum, Knapsack, and more generally Integer Programming. These problems are ubiquitous, arising in everyday tasks such as scheduling events without collision, industrial logistics, and even post-quantum cryptography, where the hardness of Subset Sum underpins security against quantum attacks. 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 was to leverage recent advances in theoretical computer science to design faster, and in many cases best-possible algorithms for these fundamental optimization problems to lay the foundations for next-generation solvers. To this end, we developed 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 successfully applied this approach to open problems on exact, parameterized, and approximation algorithms. We demonstrated that:
While focusing on the classic optimization problems Subset Sum and Knapsack, we demonstrated via numerous examples that our approach is viable across a wide range of problem domains including graphs, string, geometry, and databases. We also utilized the insights of practical integer programming solvers to obtain highly-efficient implementations for curve similarity.
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 was running from 11/2019-11/2025.
Karl Bringmann: Principal Investigator
Nick Fischer: PhD student from 01/20 to 03/23
Vasileios Nakos: Postdoc from 02/20 to 11/21
Alejandro Cassis: PhD student from 06/20 to 02/24
Karol Węgrzycki: Postdoc from 10/20 to 11/24
Evangelos Kipouridis: Postdoc from 09/22 to 11/24
Egor Gorbachev: PhD student since 03/23
Arturo Merino: Postdoc from 05/23 to 04/24
Anita Dürr: PhD student since 11/23
Yanheng Wang: PhD student since 11/23
Niko Hastrich: PhD student since 09/24
| [69] |
"Structural Parameterization of Steiner Tree Packing" STACS'26: Proc. of the 43rd International Symposium on Theoretical Aspects of Computer Science |
| [68] |
"Fine-Grained Equivalence for Problems Related to Integer Linear Programming" ITCS'25: Proc. of the 16th Innovations in Theoretical Computer Science Conference |
| [67] |
"A Faster Algorithm for Constrained Correlation Clustering" STACS'25: Proc. of the 42nd International Symposium on Theoretical Aspects of Computer Science |
| [66] |
"Near-Optimal Directed Low-Diameter Decompositions" ICALP'25: Proc. of the 52nd International Colloquium on Automata, Languages, and Programming |
| [65] |
"Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation" SoCG'25: Proc. of the 41st International Symposium on Computational Geometry |
| [64] |
"Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds" ESA'25: Proc. of the 33rd Annual European Symposium on Algorithms |
| [63] |
"Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications" ESA'25: Proc. of the 33rd Annual European Symposium on Algorithms |
| [62] |
"A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends" STOC'25: Proc. of the 57th ACM Symposium on the Theory of Computing |
| [61] |
"Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights" STOC'25: Proc. of the 57th Annual ACM Symposium on Theory of Computing |
| [60] |
"Beating Bellman's Algorithm for Subset Sum" SODA'25: Proc. of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [59] |
"A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints" SODA'25: Proc. of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms |
| [58] |
"Clustering to Minimize Cluster-Aware Norm Objectives" SODA'25: Proc. of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms |
| [57] |
"Generating All Invertible Matrices by Row Operations" ISAAC'24: Proc. of the 35th International Symposium on Algorithms and Computation |
| [56] |
"The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds" ITCS'24: Proc. of the 15th Innovations in Theoretical Computer Science conference Invited to TheoretiCS |
| [55] |
"The Tractability Border of Reachability in Simple Vector Addition Systems with States" FOCS'24: Proc. of the 65th IEEE Annual Symposium on Foundations of Computer Science |
| [54] |
"Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems" FOCS'24: Proc. of the 65th IEEE Annual Symposium on Foundations of Computer Science |
| [53] |
"Separator Theorem and Algorithms for Planar Hyperbolic Graphs" SoCG'24: Proc. of the 40th International Symposium on Computational Geometry |
| [52] |
"Fine-Grained Complexity of Earth Mover's Distance under Translation" SoCG'24: Proc. of the 40th International Symposium on Computational Geometry Invited to JoCG special issue |
| [51] |
"Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments" ESA'24: Proc. of the 32nd Annual European Symposium on Algorithms |
| [50] |
"Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing" ESA'24: Proc. of the 32nd Annual European Symposium on Algorithms Best paper award of ESA Track A |
| [49] |
"Knapsack with Small Items in Near-Quadratic Time" STOC'24: Proc. of the 56th ACM Symposium on the Theory of Computing |
| [48] |
SODA'24: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms |
| [47] |
"Faster Sublinear-Time Edit Distance" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [46] |
"Approximating Subset Sum Ratio faster than Subset Sum" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [45] |
"The Time Complexity of Fully Sparse Matrix Multiplication" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [44] |
"Dynamic Dynamic Time Warping" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [43] |
"Coverability in 2-VASS with One Unary Counter is in NP" FoSSaCS'23: Proc. of the 26th International Conference on Foundations of Software Science and Computation Structures |
| [42] |
"Dynamic Data Structures for Parameterized String Problems" STACS'23: Proc. of the 40th International Symposium on Theoretical Aspects of Computer Science |
| [41] |
"Optimal Algorithms for Bounded Weighted Edit Distance" FOCS'23: Proc. of the 64th IEEE Annual Symposium on Foundations of Computer Science |
| [40] |
"Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!" FOCS'23: Proc. of the 64th Annual IEEE Symposium on Foundations of Computer Science |
| [39] |
"Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution" ESA'23: Proc. of the 31st Annual European Symposium on Algorithms |
| [38] |
"Fitting Tree Metrics with Minimum Disagreements" ESA'23: Proc. of the 31st Annual European Symposium on Algorithms |
| [37] |
"Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality" ICALP'23: Proc. of the 50th International Colloquium on Automata, Languages, and Programming |
| [36] |
"Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics" STOC'23: Proc. of the 55th ACM Symposium on the Theory of Computing Invited to SICOMP special issue |
| [35] |
SODA'23: Proc. of the 2023 ACM-SIAM Symposium on Discrete Algorithms |
| [34] |
"Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms" SODA'23: Proc. of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [33] |
"Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [32] |
"Improved Sublinear-Time Edit Distance for Preprocessed Strings" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [31] |
"A Structural Investigation of the Approximability of Polynomial-Time Problems" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [30] |
"Computing Generalized Convolutions Faster Than Brute Force" IPEC'22: Proc. of the 7th International Symposium on Parameterized and Exact Computation |
| [29] |
"Tight Fine-Grained Bounds for Direct Access on Join Queries" 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" SoCG'22: Proc. of the 38th International Symposium on Computational Geometry |
| [27] |
"Towards sub-quadratic diameter computation in geometric intersection graphs" SoCG'22: Proc. of the 38th International Symposium on Computational Geometry |
| [26] |
"Isolation Schemes for Problems on Decomposable Graphs" STACS'22: Proc. of the 39th International Symposium on Theoretical Aspects of Computer Science |
| [25] |
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" STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing |
| [23] |
"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution" 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" SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [21] |
"Fine-Grained Completeness for Optimization in P" 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" CiE'21: Proc. of the 17th Conference on Computability in Europe |
| [19] |
"A Gap-ETH-Tight Approximation Scheme for Euclidean TSP" FOCS'21: Proc. of the 62nd Annual IEEE Symposium on Foundations of Computer Science |
| [18] |
"Fast n-fold Boolean Convolution via Additive Combinatorics" 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" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming |
| [16] |
"Knapsack and Subset Sum with Small Items" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming |
| [15] |
"On the Approximability of Multistage Min-Sum Set Cover" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming |
| [14] |
"A Linear-Time n0.4-Approximation for Longest Common Subsequence" 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" 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" 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" SoCG'21: Proc. of the 37rd International Symposium on Computational Geometry Invited to JoCG special issue |
| [10] |
SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [9] |
"A Fine-Grained Perspective on Approximating Subset Sum and Partition" SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [8] |
"On Near-Linear-Time Algorithms for Dense Subset Sum" SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [7] |
"Fast and Simple Modular Subset Sum" SOSA@SODA'21: Proc. of the 4th SIAM Symposium on Simplicity in Algorithms |
| [6] |
"Impossibility Results for Grammar-Compressed Linear Algebra" NeurIPS'20: Proc. of the 34th Annual Conference on Neural Information Processing Systems |
| [5] |
"Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time" FOCS'20: Proc. of the 61st Annual IEEE Symposium on Foundations of Computer Science |
| [4] |
ESA'20: Proc. of the 28th Annual European Symposium on Algorithms |
| [3] |
"Scheduling Lower Bounds via AND Subset Sum" ICALP'20: Proc. of the 47th International Colloquium on Automata, Languages, and Programming |
| [2] |
"Faster Minimization of Tardy Processing Time on a Single Machine" 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" STOC'20: Proc. of the 52nd ACM Symposium on the Theory of Computing |