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

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 183875639

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.

• DFG Programme: Research Grants