Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing

Klaus Jansen, Malin Rau

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 $P…