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

我们研究了各种排序和布局问题。在调度问题中，人们必须将一组给定的作业和相关的运行时间分配给可用的机器。优化目标通常是提前完成所有作业。包装问题涉及将物品装入容量有限的箱子中，同时使成本最小化，例如，成本会随着用于包装所有物品的箱子的数量或大小而增加。这类问题的最优解的计算耗时太长，对于许多应用来说是不可行的。因此，已经并将继续努力开发更快的算法。通常情况下，性能增长在一些发展之后会减慢甚至停止。我们怀疑这是由于问题本身的复杂性，而且存在即使是最好的算法也无法克服的障碍。我们的主要目标是找到并系统地描述调度和布局问题的障碍，从而证明某些快速算法是不存在的。计算复杂性理论中的一个基本问题是3-SAT。它包括找出真值“真”和“假”对给定公式的变量的赋值，从而满足该公式。专家中流行的观点是，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.