Fine-grained complexity and algorithms for scheduling and packing

用于调度和打包的细粒度复杂性和算法

• 批准号: 453769249
• 负责人: Professor Dr. Klaus Jansen
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/453769249?language=en
• 关键词: Fine; grained; complexity; algorithms; scheduling

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.

排程与装箱问题是计算机科学、数学和运筹学中研究最活跃、最深入的问题之一。在过去的几十年里，成千上万的研究论文研究了这些问题，从而产生了许多解决这些问题的算法。一些算法可以精确地解决问题，一些算法只能近似最优解，一些算法只能解决特殊情况。所有这些算法给出了上界的各种包装和调度问题的复杂性，无论是在运行时间方面需要找到最佳的解决方案，或者是它在多项式时间内实现的解决方案的质量。相比之下，证明相应的下界传统上是困难的，因为假设P不等于NP是不够强的这样bounds.In过去的十年中，一些更强大的说明NP难问题的复杂性被开发。最著名的是指数时间假设（ETH），它指出经典的3-SAT问题不能在时间2^{o（n）}内解决。基于这一假设，一些突破性的结果显示了某些算法的最优性或暗示了改进的可能性。在本项目中，我们希望将这些技术转移到运筹学领域。我们的目标是开发一个框架，以显示调度和包装问题的重要算法的最优性，精确算法和近似算法。此外，在框架暗示改进的可能性，我们的目标是更好的算法匹配构造的下限。为了促进算法改进的研究，我们的目标也是解决长期悬而未决的问题，调度和几何包装问题的近似性。