Fine-grained complexity and algorithms for scheduling and packing

点击翻译按钮获取中文摘要

Scheduling and packing problems are among the most actively and thoroughly studied problems in computer science, mathematics, and operations research. Thousands of research papers have investigated these problems 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. All of these algorithms give upper bounds on the complexity of the various packing and scheduling problems, be it in terms of running time required to find optimal solutions or be it 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 unequal NP is not strong enough for such bounds.In the last decade, several stronger conjectures about the complexity of NP-hard problems were developed. Most famously is the exponential-time hypothesis (ETH) that states that the classical 3-SAT problem can not be solved in 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.