Advertisement
Published in:
2019 | OriginalPaper | Chapter
Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing
Authors : Klaus Jansen, Malin Rau
Published in: Euro-Par 2019: Parallel Processing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We study the Multiple Cluster Scheduling problem and the Multiple Strip Packing problem. For both problems, there is no algorithm with approximation ratio better than 2 unless \(\mathrm {P}= \mathrm {NP}\). In this paper, we present an algorithm with approximation ratio 2 and running time \(\mathcal {O}(n)\) for both problems for \(N >2\) (and running time \(\mathcal {O}(n\log (n)^2)\) for \(N=2\)). While a 2 approximation was known before, the running time of the algorithm is at least \(\varOmega (n^{256})\) in the worst case. Therefore, an \(\mathcal {O}(n)\) algorithm is surprising and the best possible.
While the above result is strong from a theoretical point of view, it might not be very practical due to a large hidden constant caused by calling an AEPTAS with a constant \(\varepsilon \ge 1/8\) as subroutine. Nevertheless, we point out that the general approach of finding first a schedule on one cluster and then distributing it onto the other clusters might come in handy in practical approaches. We demonstrate this by presenting a practical algorithm with running time \(\mathcal {O}(n\log (n))\), without hidden constants, that is an approximation algorithm with ratio 9/4 if the number N of clusters is dividable by 3 and bounded by \(9/4 + \frac{3}{4N}\) otherwise.