权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

假设指数时间假设的调度和打包算法的下限

基本信息

批准号：
236400547
负责人：
Professor Dr. Klaus Jansen
金额：
--
依托单位：
Institut für Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2013
资助国家：
德国
起止时间：
2012-12-31 至 2016-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/236400547?language=en
关键词：
Lower bounds scheduling packing algorithms

项目摘要

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.

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