Structural results and their application in scheduling and packing problems

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

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.