Journal
THEORY OF COMPUTING SYSTEMS
Volume 64, Issue 1, Pages 120-140Publisher
SPRINGER
DOI: 10.1007/s00224-019-09910-6
Keywords
Parallel Task Scheduling; Strip Packing; 3-Partition; Inapproximability; Complexity
Categories
Funding
- German Research Foundation (DFG) project [JA 612 /20-1]
Ask authors/readers for more resources
We study Parallel Task Scheduling Pm sizej Cmax 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 for approximating pseudo-polynomial Strip Packing to 54. Since the best known approximation algorithm for this problem has a ratio of 54 + e, 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available