Algorithms and Complexity Seminar

(Acyclic) Job Shops are Hard to Approximate

Ola Svensson (IDSIA)

Currently, the best approximation algorithms for job shops have slightly worse than logarithmic performance guarantee, and the only known inapproximability result says that it is NP-hard to approximate acyclic job shops within a factor less than 5/4.
We narrow this gap by providing new inapproximability results. More specifically, we show that the (acyclic) job shop problem cannot be approximated within ratio $O(\log^{1-\epsilon} lb)$, unless NP has (randomized) quasi-polynomial algorithms, and where lb denotes a trivial lower bound on the optimal value. This almost matches the best known results for acyclic job shops, since an $O(\log^{1+\epsilon} lb)$-approximate solution can be obtained in polynomial time.
Recently, a PTAS was given for the job shop problem, where the number of machines and the number of operations per job are assumed to be constant. We show that both these restrictions are necessary to obtain a PTAS, even in the preemptive case, i.e., when jobs are allowed to be interrupted.
Joint work with Monaldo Mastrolilli.

Host: Andreas S. Schulz