Fine-grained complexity and algorithms for scheduling and packing

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 453769249

Scheduling and packing problems are among the most actively and thoroughly studied problems in computer science, mathematics, and operations research. Thousands of research papers concerning these problems have been published in the last decades, leading to a multitude of algorithms for solving them. Some algorithms solve the problems exactly, some only approximate the optimal solution, some solve only special cases in polynomial time. All of these algorithms give upper bounds on the complexity of the various packing and scheduling problems - in terms of the running time required to find an optimal solution or in terms of the solution quality achievable in polynomial time. In contrast, proving corresponding lower bounds has traditionally been difficult, as the assumption that P does not equal NP is not strong enough for such bounds. In the last three decades, several stronger conjectures about the complexity of NP-hard problems were developed. Most famous is the exponential-time hypothesis (ETH), which states that the classical 3-SAT problem can not be solved in sub-exponential time 2^{o(n)}. Based upon this hypothesis, some breakthrough results were achieved that showed the optimality of certain algorithms or hinted at the possibility of improvements. In this project, we want to transfer these techniques to the field of operations research. We aim to develop a framework to show the optimality of important algorithms for scheduling and packing problems, both for exact algorithms and for approximation algorithms. Furthermore, where the framework hints at the possibility of improvements, we aim to give better algorithms matching the constructed lower bounds. To facilitate this study of algorithmic improvements, we aim to also tackle long-standing open questions regarding the approximability of scheduling and geometric packing problems.

• DFG Programme: Research Grants