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