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

我们的研究项目的主要目标是设计和分析重要调度和装箱问题的近似方案。对于许多NP-Hard优化问题，都有多项式时间近似格式(PTA)，使得对于任意精度和输入的$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\geq0$是尽可能小的.这将接近该调度问题的近似方案的运行时间的已知下界。此外，我们还想研究随着时间推移作业到达的在线调度。随着新工作的到来，几个已经安排好的工作可能会被重新打包。我们的目标是设计一个高效健壮的在线算法，其多项式迁移因子为$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的运行时间。此外，我们考虑一种称为下料的箱子包装变种，在这种情况下，我们只有固定数量的$m$不同尺寸的物品。我们的目标是设计一种算法，该算法最多只需要比最优解多一个仓，并且运行时间仅为$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.