Given a sequence of n positive integers w1,w2,..., wn that are associated with the items 1,2,...,n respectively. In the windows scheduling problem, the goal is to schedule all the items (equal length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi slots (a slot is the transmission time of one page). In the unit fraction bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/wi. The optimization objective is to minimize the number of channels or bins.
In the off-line setting the sequence is known in advance whereas in the on-line setting the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/wi of the channel's bandwidth, it follows that windows scheduling without migration (all broadcasts of a page must be from the same channel) is a restricted version of unit fractions bin packing.
The talk considers the relationship between windows-scheduling and unit-fraction bin-packing, by presenting upper and lower bounds for each of these problems in the online and offline settings.
Joint work with Amotz Bar-Noy and Richard Ladner.