max planck institut
informatik
informatik
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.
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
| [32] |
"Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [31] |
"Improved Sublinear-Time Edit Distance for Preprocessed Strings" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [30] |
"A Structural Investigation of the Approximability of Polynomial-Time Problems" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [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] |
"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 |
| [6] |
"Fast and Simple Modular Subset Sum" SOSA@SODA'21: Proc. of the 4th SIAM Symposium on Simplicity in Algorithms |
| [5] |
"Impossibility Results for Grammar-Compressed Linear Algebra" NeurIPS'20: Proc. of the 34th Annual Conference on Neural Information Processing Systems |
| [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 |
| [5] |
"Faster Minimization of Tardy Processing Time on a Single Machine" Algorithmica, 2022 |
| [4] |
"Scheduling Lower Bounds via AND Subset Sum" Journal of Computer and System Sciences, 2022 |
| [3] |
"SETH-based Lower Bounds for Subset Sum and Bicriteria Path" ACM Transactions on Algorithms, 2022 Special issue of SODA'19 |
| [2] |
"Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance" Journal of Computational Geometry, 2021 |
| [1] |
"Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm" ACM Transactions on Algorithms, 2021 |