Lower bounds for scheduling and packing algorithms assuming the exponential time hypothesis

我们研究了各种调度和包装问题。在调度问题中，必须将给定的一组具有相关运行时间的作业分配给可用的机器。优化目标通常是尽早完成所有作业。包装问题包括将物品装入容量有限的箱子中，同时使成本最小化，例如，成本随着用于包装所有物品的箱子的数量或大小而增加。这类问题的最优解的计算时间太长，对许多应用来说是可行的。因此，人们一直在努力并将继续努力开发更快的算法。通常情况下，性能提升会在一些开发后减慢甚至停止。我们怀疑这是由于问题固有的复杂性，并且存在无法克服的障碍，即使是最好的算法。我们的主要目标是系统地发现和描述调度和包装问题的这些障碍，从而证明某些快速算法不可能存在。计算复杂性理论中的一个基本问题是3-SAT。它包括找到对给定公式的变量的真值“true”和“false”的赋值，使公式满足。专家们普遍认为，3-SAT要求运行时间在待解变量数量上严格呈指数级增长。这种说法也被称为指数时间假设。我们想把3-SAT问题转化为不同的调度和包装问题。这使得3-SAT可以通过相应的调度或包装问题的算法来解决。我们可以证明这种转换在调度或包装问题上转移了最小的运行时间。除了精确算法（总是产生最优解）之外，近似算法与实际目的高度相关。对于他们来说，允许在一定范围内偏离最优解，以换取大大减少的运行时间。我们想找到这两种算法的运行时间的下界。我们希望这将显示一些已知算法的最优性。然而，在许多情况下，我们怀疑算法还不是最优的，我们想尝试改进以前已知的算法。我们的目标是缩小可实现的运行时间和可证明的下界之间的差距，并最终完全消除它们。精确算法虽然运行时间长，但在逼近算法的发展中有着广泛的应用。它们中的许多都是为问题的一小部分计算最优解。因此，精确算法的进步可以直接提高近似算法产生的解的质量。

We investigate various scheduling and packing problems. In scheduling problems one has to assign a given set of jobs with associated running times to available machines. The optimization target is usually the early completion of all jobs. Packing problems involve packing items into bins of limited capacity while minimizing the costs, which are for example increased with the number or size of the bins used to pack all items. The computation of optimal solutions to such problems takes too long to be feasible for many applications. Thus, efforts have been and continue to be made to develop faster algorithms. Oftentimes, the performance increase slows down or even stops after some development. We suspect that this is due to the complexity inherent to the problems, and that there exist barriers that can not be overcome, even by the best algorithms. Our primary objective is to find and describe these barriers for scheduling and packing problems systematically and thus prove that certain fast algorithms can not exist.A fundamental problem in the theory of computation complexity is 3-SAT. It consists of finding an assignment of the truth-values 'true' and 'false' to the variables of a given formula such that the formula is satisfied. The prevalent opinion among experts is that 3-SAT requires a running time strictly exponential in the number of variables to be solved. This statement is also known as exponential time hypothesis. We want to transform the 3-SAT problem such that it can be expressed as different scheduling and packing problems. This allows 3-SAT to be solved by algorithms for the corresponding scheduling or packing problem. One can prove that this transformation transfers the minimum running time on the scheduling or packing problem.In addition to exact algorithms, that always produce an optimal solution, approximation algorithms are highly relevant for practical purposes. For them it is allowed to deviate within certain bounds from the optimal solution in exchange for a greatly reduced running time. We want to find lower bounds on the running times for both types of algorithms. We hope that this will show the optimality of some known algorithms. In many cases however, we suspect that the algorithms are not yet optimal, and we want to try to improve upon the previously known algorithms. Our aim is to narrow the gaps between achievable running times and provable lower bounds and eventually close them completely. Despite their long running time, exact algorithms have applications in the development of approximation algorithms. Many of them compute an optimal solution for a small part of the problem. Thus an advancement in exact algorithms can directly improve the quality of the solutions produced by approximation algorithms.