Henning, Sören, Jansen, Klaus, Rau, Malin and Schmarje, Lars (2017) Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. Lecture Notes in Computer Science, 10846 . DOI 10.1007/978-3-319-90530-3_15.

Full text not available from this repository.

Abstract

We study the Parallel Task Scheduling problem 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 1211 for approximating pseudo-polynomial Strip Packing to 54. Since the best known approximation algorithm for this problem has a ratio of 43+ε, this result narrows the gap between approximation ratio and inapproximability result by a significant step. Both results are proven by a reduction from the strongly NP-complete problem 3-Partition.

Document Type:	Article
Research affiliation:	Kiel University > Kiel Marine Science OceanRep > The Future Ocean - Cluster of Excellence Kiel University > Software Engineering Kiel University
Refereed:	Yes
Open Access Journal?:	Yes
Publisher:	American Medical Association
Date Deposited:	19 Dec 2017 10:21
Last Modified:	23 Sep 2019 17:37
URI:	https://oceanrep.geomar.de/id/eprint/40870

Actions (login required)

View Item