Frontiers of Packing: Transfer of Methods and Algorithms

• Applicant: Dr. Karol Wegrzycki
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 559177164

Packing problems, ubiquitous in computer science, challenge researchers to efficiently fit objects into containers across diverse domains such as optimization, computational geometry, operations research, and computational logic. However, exact methods and ideas often remain isolated within specific communities of theoretical computer science (TCS). In this project, we aim to transfer the knowledge and methodologies of packing problems between these fields. Our goal is to identify general-usage techniques and tractability borders. We will address four key focus areas: Optimization: improving the complexity of Knapsack-type problems. Computational Geometry: adapting approximation techniques for geometric settings. Operations Research: refining exact solution methods for scheduling problems. Computational Logic: exploring the fine-grained complexity of problems in computational logic. Our plan is to adapt methodologies from the respective fields. For example, to solve the Knapsack problem, we plan to use methods from cryptography. To improve algorithms in geometry or computational logic, we plan to utilize tools developed in optimization to better bound the number of states of dynamic programming. Similarly, we aim to use insights from parameterized algorithms and graph theory to enhance algorithms in operations research for scheduling problems. We hope that through rigorous analysis, our project accelerates collaboration between these fields and uncovers deeper understanding across different domains of theoretical computer science.

• DFG Programme: Emmy Noether Independent Junior Research Groups