Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
We study Parallel Task Scheduling P m s i z e j C max with a constant number of machines. This problem is known to be strongly NP complete for each m 5, while it is solvable in pseudo polynomial time for each m 3. We give a positive answer to the long standing open question whether this problem is strongly NP complete for m 4. As a second result, we improve the lower bound of 12 11 \frac {12}{11} for approximating pseudo polynomial Strip Packing to 5 4 \frac {5}{4} Since the best known approximation algorithm for this problem has a ratio of 5 4 e \frac {5}{4} \varepsilon this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP complete problem 3 Partition.
Theory of Computing Systems