2019/02/09 by Klaus Jansen, Jansen, Klaus, Malin Rau +1
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1902.03428
openalex publication_date 2019/02/09 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
We study the Multiple Cluster Scheduling problem and the Multiple Strip\nPacking problem. For both problems, there is no algorithm with approximation\nratio better than 2 unless P = NP. In this paper, we present an algorithm\nwith approximation ratio 2 and running time O(n) for both problems. While a\n2 approximation was known before, the running time of the algorithm is at\nleast \Ω(n256) in the worst case. Therefore, an O(n) algorithm is\nsurprising and the best possible. We archive this result by calling an AEPTAS\nwith approximation guarantee (1+\ε)OPT +p\max and running time of\nthe form O(n\log(1/\ε)+ f(1/\ε)) with a constant\n\ε to schedule the jobs on a single cluster. This schedule is then\ndistributed on the N clusters in O(n). Moreover, this distribution\ntechnique can be applied to any variant of of Multi Cluster Scheduling for\nwhich there exists an AEPTAS with additive term p\max.\n While the above result is strong from a theoretical point of view, it might\nnot be very practical due to a large hidden constant caused by calling an\nAEPTAS with a constant \ε \≥ 1/8 as subroutine. Nevertheless, we\npoint out that the general approach of finding first a schedule on one cluster\nand then distributing it onto the other clusters might come in handy in\npractical approaches. We demonstrate this by presenting a practical algorithm\nwith running time O(n\log(n)), with out hidden constants, that is a\n9/4-approximation for one third of all possible instances, i.e, all instances\nwhere the number of clusters is dividable by 3, and has an approximation\nratio of at most 2.3 for all instances with at least 9 clusters.\n