Structural results and their application in scheduling and packing problems

结构结果及其在调度和打包问题中的应用

• 批准号: 335406402
• 负责人: Professor Dr. Klaus Jansen
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2017
• 资助国家: 德国
• 起止时间: 2016-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/335406402?language=en
• 关键词: Structural; results; their; application; scheduling

The main focus of this project is to find structural results for integer linear programs (ILPs). Our goal is to prove the existence of optimal solutions of the respective ILP with a very specific shape. For example, we want to show there are always optimal solutions which have a bounded number of non-zero components or limited weight on certain components. Using the existence of solutions with this shape, one can search specifically for them and therefore solve the ILP more efficiently.In this project, we focus on ILP formulations that arise from concrete algorithmic problems like bin packing. In this proposal we investigate structural properties which are can be used to solve open algorithmic questions. For example, we hope to find an FPT algorithm for the bin packing problem parameterized by the number d of different item sizes with running time 2^2^O(d) |I|^O(1), where |I| is the encoding length of instance I. This would improve upon the result by Goemans and Rothvoß who proved polynomiality for bin packing when the number d of different item sizes is constant. Their algorithm has a running time of |I|^2^O(d). Furthermore, we want to prove structure results for the case when only approximate solutions are needed. With this an algorithm for the bin packing problem can be found which has a running time of 2^d |I|^O(1) and approximation guarantee OPT+1, where OPT is the value of an optimal solution. For the scheduling problem on identical machines, this could imply an algorithm with running time 2^d |I|^O(1) and approximation guarantee (1+epsilon) OPT. One of our greater aims of this project is to prove or disprove the so called modified roundup property (MRP) of the Gilmore-Gomory ILP for the bin packing problem via investigations on the structure. The MRP is a prominent conjecture and states that the objective value of the ILP is at most the objective value of the linear program relaxation rounded up plus 1.In general, structural results can be applied to a wide range of applications and algorithmic problems. We believe that these techniques can become an important part of the algorithmic toolset to develop efficient algorithms.

这个项目的主要重点是寻找整数线性规划（ILP）的结构结果。我们的目标是证明一个非常具体的形状的相应的ILP的最优解的存在性。例如，我们想证明总是存在最优解，这些最优解具有有限数量的非零分量或某些分量的有限权重。利用这种形状的解决方案的存在性，人们可以专门搜索它们，从而更有效地解决ILP。在这个项目中，我们专注于ILP公式，从具体的算法问题，如装箱。在这个建议中，我们调查的结构特性，可用于解决开放的算法问题。例如，我们希望找到一个FPT算法，用于由不同物品大小的数量d参数化的装箱问题，运行时间为2^2^O（d）。|我|^O（1），其中|我|是实例I的编码长度。这将改善Goemans和Rothvovich的结果，他们证明了当不同项目大小的数量d是常数时装箱的多项式。他们的算法的运行时间为|我|^2^O（d）.此外，我们要证明结构的情况下，只需要近似解。由此可以找到一个求解装箱问题的算法，其运行时间为2^d|我|^O（1）和近似保证OPT+1，其中OPT是最优解的值。对于相同机器上的调度问题，这可能意味着运行时间为2^d的算法|我|^O（1）和近似保证（1+ ∞）OPT.我们的一个更大的目标是通过对Gilmore-Gomory ILP的结构的研究来证明或反驳Gilmore-Gomory ILP对于装箱问题的所谓修正的舍入性质（MRP）. MRP是一个著名的猜想，它指出ILP的目标值至多是线性规划松弛的目标值四舍五入加1。一般来说，结构性结果可以应用于广泛的应用和算法问题。我们相信，这些技术可以成为算法工具集的重要组成部分，以开发高效的算法。