Nearly optimal perfectly periodic schedules

We consider the problem of scheduling a set of pages on a single broadcast channel using time-multiplexing. In a perfectly periodic schedule, time is divided into equal size slots, and each page is transmitted in a time slot precisely every fixed interval of time (the period of the page). We study the case in which each page i has a given demand probability w(i), and the goal is to design a perfectly periodic schedule that minimizes the average time a random client waits until its page is transmitted. We seek approximate polynomial solutions. Approximation bounds are obtained by comparing the costs of a solution provided by an algorithm and a solution to a relaxed (non-integral) version of the problem. A key quantity in our methodology is a fraction we denote by a(1), that depends on the maximum demand probability: a(1) =(def) rootmax(i) {w(i)}/Sigmarootw(i). The best known polynomial algorithm to date guarantees an approximation of 3/2 + 3/2 a(1). In this paper, we develop a tree-based methodology for perfectly periodic scheduling, and using new techniques, we derive algorithms with better bounds. For small a, values, our best algorithm guarantees approximation of 1 + (3)root3a(1)/1-(3)root2a(1). On the other hand, we show that the integrality gap between the cost of any perfectly periodic schedule and the cost of the fractional problem is at least 1 + a(1)(2). We also provide algorithms with good performance guarantees for large values of a(1).