Design of Efficient Polynomial Time Approximation Schemes for Scheduling and Related Optimization Problems

我们研究项目的主要目标是设计和分析重要的调度和装箱问题的近似方案。对于许多NP-hard优化问题，有多项式时间近似方案（PTAS），这样在任何精度$\epsilon > 0$和输入$I$下都可以找到接近最优的解。对于较小的$\epsilon > 0$，大多数近似方案的运行时间都很长，无法在实际中应用。一个例子是Hochbaum和Shmoys在运行时间为$(n/\epsilon)^{O(1/\epsilon^2)}$的相同机器上调度的近似方案。目标是开发有效的近似方案，其运行时间为$f(1/\epsilon) poly(n)$，值为$f(1/\epsilon)$，越小越好。对于相同/统一机器上的调度，我们希望开发一种有效的多项式时间近似方案（EPTAS），其运行时间为$2^{O(1/\epsilon \log^c(1\epsilon))} + poly(n)$，其中$c \geq 0$尽可能小。这将接近这个调度问题的近似方案的运行时间的已知下界。此外，我们想要研究在线调度，作业随时间到达的位置。当一份新工作到来时，一些已经安排好的工作可能会被重新打包。我们的目标是在$1/\epsilon$中设计一个有效的具有多项式迁移因子的鲁棒在线算法。迁移因子由重新包装的项目的大小除以到达的项目的大小来定义。最著名的鲁棒在线调度算法在$1/\epsilon$中有一个迁移因子指数。装箱的近似格式有一个附加常数$g(1/\epsilon)$；例如：$A_\epsilon(I) \leq (1+\epsilon) OPT(I) + g(1/\epsilon)$。其优点是运行时间由$n$和$1/\epsilon$中的多项式限定。这些格式称为渐近全多项式时间逼近格式（AFPTAS）。对于装箱，我们希望提高添加剂常数$g(1/\epsilon)$以及现有AFPTAS的运行时间。此外，我们考虑的bin包装变体称为切割库存，其中我们只有固定数量的$m$不同的项目尺寸。我们的目标是设计一种算法，该算法与最优解相比最多只需要一个额外的bin，并且其运行时间仅为$m$中的单指数。最后，我们将实现所开发的算法，并使用算法工程的方法对其进行分析。

The main goal of our research project is the design and analysis of approximation schemes for important scheduling and bin packing problems. There are polynomial time approximation schemes (PTAS) for many NP-hard optimization problems such that a solution near the optimum can be found for any accuracy $\epsilon > 0$ and input $I$. For small $\epsilon > 0$, most of the approximation schemes have a huge running time such that they cannot be applied in practice. An example is the approximation scheme by Hochbaum and Shmoys for scheduling on identical machines with running time $(n/\epsilon)^{O(1/\epsilon^2)}$. The goal is to develop efficient approximation schemes, which have a running time of the form $f(1/\epsilon) poly(n)$ with a value $f(1/\epsilon)$ as small as possible.For scheduling on identical/uniform machines, we want to develop an efficient polynomial time approximation scheme (EPTAS) with running time $2^{O(1/\epsilon \log^c(1\epsilon))} + poly(n)$ where $c \geq 0$ is as small as possible. This would be close to the best known lower bound for the running time of an approximation scheme for this scheduling problem. Moreover, we want to investigate online scheduling where jobs arrive over time. As a new job arrives, several already placed jobs may be repacked. Our goal is the design of an efficient robust online algorithm with a polynomial migration factor in $1/\epsilon$. The migration factor is defined by the size of the repacked items divided by the size of the arriving item. The best known algorithm for the robust online scheduling problem has a migration factor exponential in $1/\epsilon$.The approximation schemes for bin packing have an additional constant $g(1/\epsilon)$; i.e. $A_\epsilon(I) \leq (1+\epsilon) OPT(I) + g(1/\epsilon)$. The advantage is that the running time is bounded by a polynomial in $n$ and $1/\epsilon$. These schemes are called asymptotic fully polynomial time approximation schemes (AFPTAS). For bin packing, we want to improve the additive constant $g(1/\epsilon)$ as well as the running time of existing AFPTAS. Additionally, we consider the bin packing variant called cutting stock where we have only a constant number of $m$ different item sizes. Our goal is the design of an algorithm that needs at most one additional bin compared to the optimal solution and whose running time is only single exponential in $m$.Finally, we will implement the developed algorithms and analyze them using methods of algorithm engineering.