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

我们的研究项目的主要目标是设计和分析的近似方案的重要调度和装箱问题。有多项式时间近似计划（PTAS）的许多NP-难优化问题，这样一个解决方案接近最佳可以找到任何精度$\displaystyle $0 $和输入$I$。对于小的$\displaystyle> 0$，大多数的近似方案有一个巨大的运行时间，使他们不能在实际中应用。一个例子是Hochbaum和Shmoys的近似计划，用于运行时间为$（n/\n）^{1/\epsilon ^2}$的相同机器上的调度。我们的目标是开发有效的近似方案，其运行时间为$f（1/\n）poly（n）$，值为$f（1/\n）$尽可能小。对于相同/统一机器上的调度，我们想要开发一个高效的多项式时间逼近方案（EPTAS），运行时间为$2^{O（1/\n\log^c（1\n））} + poly（n）$其中$c \geq 0$尽可能小。这将是接近最好的已知的运行时间为这个调度问题的近似方案的下限。此外，我们想研究在线调度，工作随着时间的推移到达。当一个新的工作到达时，几个已经放置的工作可能会被重新打包。我们的目标是设计一个有效的强大的在线算法的多项式迁移因子在1/\n $。迁移因子由重新包装的物品的大小除以到达物品的大小来定义。最著名的鲁棒在线调度问题的算法有一个迁移因子指数为1/\n $。装箱的近似方案有一个额外的常数g（1/\n）$;即$A_\n（I）\leq（1+\n）OPT（I）+ g（1/\n）$。其优点是运行时间由$n$和$1/\n $中的多项式限制。这些方案被称为渐近完全多项式时间近似方案（AFPTAS）。对于装箱，我们希望改进加法常数g（1/\n）以及现有AFPTAS的运行时间。此外，我们考虑称为切割库存的装箱变体，其中我们只有恒定数量的$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.