Structural results and their application in scheduling and packing problems

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

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.