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

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

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.