Improved approximation algorithms for minimum-space advertisement scheduling

We study a scheduling problem involving the optimal placement of advertisement images in a shared space over time. The. problem is a generalization of the classical scheduling problem Pparallel toC(max), and involves scheduling each job on a specified number of parallel machines (not necessarily simultaneously) with a goal of minimizing the makespan. In 1969 Graham showed that processing jobs in decreasing order. of size, assigning each to the currently-least-loaded machine, yields a 4/3-approximation for Pparallel toC(max). Our main result is a proof that the natural, generalization of Graham's algorithm also yields a 4/3-approximation to the minimum-space advertisement scheduling problem. Previously, this algorithm was only known to give an approximation ratio of 2, and the best known approximation ratio for any algorithm for the minimum-spacead scheduling problem was 3/2. Our proof requires a number of new structural, insights, which leads to a new lower bound for the problem and a non-trivial linear programming relaxation. We also provide a pseudo-polynomial approximation scheme for the problem (polynomial in the size of the problem and the number of machines).