Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing.

Henning, Sören, Jansen, Klaus, Rau, Malin and Schmarje, Lars (2017) Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. Cornell University Library .

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 > Software Engineering
Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Kiel University
Refereed: Yes
Open Access Journal?: Yes
Date Deposited: 19 Dec 2017 10:21
Last Modified: 18 Dec 2018 07:46
URI: http://oceanrep.geomar.de/id/eprint/40870

Actions (login required)

View Item View Item