Windows Scheduling as a Restricted Version of Bin Packing Amotz Bar-Noy Abstract Given is 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 fractions 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 ob jective 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. Let H = n 1 (1/wi ) be the obvious bandi= width lower bound on the required number of bins (channels). Previously an H + O(ln H ) off-line algorithm for the windows scheduling problem was known. This paper presents an H + 1 off-line algorithm to the unit fractions bin packing problem. In he on-line setting, this paper presents an t H + O( H ) algorithm to both problems where the one for the unit fractions bin packing problem is simpler. On the other hand, this paper shows that already for the unit fractions bin packing problem, any on-line algorithm must use at least H + (ln H ) bins. Richard E. Ladner 1 Intro duction Tami Tamir The input for the well known bin packing problem (BP) is a set of n item sizes s1 , s2 , . . . , sn where 0 < si < 1 for all 1 i n. The goal is to pack these items in unit size bins using as minimum as possible bins where the total size of items packed in one bin does not exceed one. We study a variant of bin packing, called the unit fractions bin packing problem (UFBP), in which all sizes are unit fractions, i.e, of the form 1/w for some integer w 2. In particular, we are interested in a packing that forms a solution to the windows scheduling problem (WS): given a sequence of n positive integers w1 , w2 , . . . , wn , called windows, that are associated with n equal length information pages (requests), the goal is to schedule all the pages on broadcasting channels such that the gap between two consecutive appearances of page i on the channels is at most wi slots, where a slot is the time to broadcast one page. For example, the sequence of windows (and page names) 2, 4, 5 can be scheduled on one channel by repeatedly transmitting the sequence [2, 4, 2, 5] and the sequence of windows 2, 3, . . . , 9 can be scheduled on two channels by repeatedly transmitting the sequence [2, 4, 2, 5] on the first channel and the sequence [3, 6, 7, 3, 8, 9] on the second channel. The following example illustrates the difference between UFBP and WS. Consider the set of windows {2, 3, 6}. Since 1/2 + 1/3 + 1/6 = 1, the three items can be packed in one bin. On the other hand, there is no windows-schedule on one channel of these pages since g cd(2, 3) = 1, and the only two ways to schedule 2 and 3 on the same channel is by repeatedly transmitting either the sequence [2, 3] or the sequence [2, 2, 3], which leaves no slots for scheduling the 6. In general, since a page requires at least 1/wi of the channel bandwidth, it follows that windows scheduling without migration (that is, when all broadcasts of a page must be from the same channel) is a restricted version of unit fractions bin packing. Computer & Information Science Department, Bro oklyn College, 2900 Bedford Ave., Bro oklyn, NY 11210. amotz@sci.bro oklyn.cuny.edu Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA 98195. {ladner, tami}@cs.washington.edu. Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 224 The goal of our work is to compare the hardness of the two problems UFBP and WS in both the on-line and the off-line settings. In particular, we present the first off-line results for UFBP and the first on-line results for both UFBP and WS. As UFBP is a special case of BP, we expect algorithms for UFBP to get better performance than the algorithms known for BP. On the other hand because WS without migrations is a restriction of UFBP, we expect algorithms for WS to have worse performance than those for UFBP. There are two difficulties in solving WS. The first is the assignment of requests to channels and the second is determining the transmission times of each request. The UFBP problem isolates the first difficulty. In a way, UFBP is the fractional version of WS that measures the power of unlimited preemptions. That is, UFBP demonstrates what can be achieved when a request is not necessarily transmitted non-preemptively in one slot, but instead can be partitioned into small segments as long as the total length of these segments in any window of wi slots is one. 1.1 Notations and Performance Analysis. a iven a sequence of item widths 1/w1 , . . . , 1/wn G nd an UFBP algorithm B , define NB ( ) to be the number of bins of unit size used by the algorithm to pack all the n items. Similarly, given a sequence of request windows w1 , . . . , wn , and a WS algorithm W , define NW ( ) to be the number of channels used by the algorithm to schedule all the n requests. Note that we use to denote both a sequence of items width 1/w1 , . . . , 1/wn for the UFBP problem, and a sequence of windows w1 , . . . , wn for the WS problem. In both cases, for all i, wi is an integer. In the off-line setting, for either UFBP or WS, the sequence is completely known to the algorithm in advance. In the on-line setting, for either UFBP or WS, the sequence is provided one element at a time and the algorithm must augment its current solution to accommodate a new element. That is, a decision that is made about which bin to pack an item in UFBP or how to schedule a request on the channels in WS, cannot be revoked once done. Let OPTB denote an optimal off-line algorithm for UFBP and OPTW denote an optimal off-line n algorithm for WS. The quantity i=1 (1/wi ) is the total width of all the elements in . Since the number of bins in UFBP and the number of channels in WS must be an integer, i n i (1/wi ) (1.1) H ( ) = =1 s a lower bound on the performance of any algorithm for UFBP and WS on the sequence . At present we do not know if the problem of finding the minimum number of bins in UFBP is NPhard, but we do know that the associated restricted form of WS is NP-hard as shown below. Thus, we seek "good" approximation algorithms for the offline UFBP and WS problems and "good" competitive algorithms for their on-line versions. Generally, we express the bounds on the performance of an algorithm A in the form (1.2) H ( ) NA ( ) H ( ) + f (H ( )) for all , where f is a non-decreasing function. These bounds translate to upper bounds on approximation and competitive ratios in a natural way: The approximation ratio for an off-line algorithm A or the competitive ratio of an on-line algorithm A is N . A ( ) (A) = sup NOPT ( ) Suppose that for algorithm A there exists a bound of the form in inequality (1.2). Since f is nondecreasing and H ( ) is a lower bound on NOPT ( ) we have: (1.3) NOPT ( ) NA ( ) NOPT ( )+f (NOPT ( )) . Hence, (A) 1 + sup {f (NOPT ( ))/NOPT ( )} . This ratio can be interesting, but does not yield as much information as inequalities (1.2) and (1.3). Consequently, we will usually express the performance of the algorithms in the paper in the form of the right inequalities of (1.2) and (1.3). 1.2 Related Work. There is a wide literature on the general bin packing problem, see the survey [9]. First, bin packing is an NP-hard problem [11]. For the off-line problem, there exists an asymptotic PTAS that uses (1 + )NOPT ( ) + 1 bins [21]. The performance of the on-line algorithms first-fit (FF) and best-fit (BF) is analyzed in [14], where it is 225 shown that (FF), (BF) 1.7. The best known lower bound for any on-line bin packing algorithm A, is (A) 1.540 [20]. The best known online bin packing algorithm is Harmonic++ whose competitive ratio is 1.589 [18]. In [8], the special case of BP with divisible item sizes (where in the sorted sequence of sizes a1 < a2 < · · ·, for all i, ai divides ai-1 ) is shown to be optimally solvable with a polynomial time algorithm. Bin packing with discrete item sizes, i.e., when items sizes are in {1/k , 2/k , . . . , j /k } for some 1 j k is considered in [7]. The windows scheduling problem was first defined in [4]. That paper shows how to construct schedules that use H ( ) + O(ln(H ( )) channels. This asymptotic result is complemented with a natural greedy algorithm that performs well in practice, but does not have a provable approximation bound. There are several interesting applications of windows scheduling. The simplest is harmonic windows scheduling where the requests represent segments of popular movies. For 1 i n, the window of segment i is wi = i, where n is the number of equal size segments the movie is partitioned into. If segment i appears in every window of i time slots, then the maximum waiting time for any client who wishes to view the movie with no interruptions is the time it takes to broadcast one segment, or 1/n of the movie length. Harmonic windows scheduling is the basis of many popular media delivery schemes (e.g., [15, 13]). This concept of receiving from multiple channels and buffering data for future playback was first developed by [22]. A variant of harmonic WS for popular movie delivery is where the movie is partitioned into n segments and the window of segment i is wi = i + d - 1 for a fixed constant d. As shown in [5], for any number of channels h, this variant can be used to construct schedules whose maximum delay is asymptotically close to the information theoretic lower bound of 1/(eh - 1) that follows from [10]. Windows scheduling can be thought of as a scheduling problem for push broadcast systems. One example is the Broadcast Disks environment (e.g., [1]) where satellites broadcast popular information pages to clients. Another example is the TeleText environment (e.g., [2]) in which running banners appear in some television networks. In such a system there are clients and servers where the servers choose what information to push and in what frequency in order to optimize the quality of service for the clients (usually the response time). In a more generalized model, the servers are not the information providers (e.g., [12, 6]). They sell their service to various providers who supply content and request that the content be broadcast regularly. The regularity can be defined by a window that translates to the maximum delay until a client receives a particular content. Windows scheduling belongs to the general class of periodic scheduling problems that has applications in many disciplines (e.g., operations research, networking). The traditional optimization goal in periodic scheduling is an "average" type goal in which a request should be scheduled 1/wi fraction of the time. The quality of an algorithm is determined by fairness issues. Among the most prominent examples are the hard real-time scheduling problem [17] and the chairman assignment problem [19]. On the other hand, the windows scheduling problem has a "max" type optimization goal in which the gap between two consecutive appearances of a request must be smaller than wi . Both optimization goals may be practical to the many applications of periodic scheduling. Note that UFBP is a relaxed version of both optimization goals. 1.3 Summary of Results. In Section 2, we prove the NP-hardness of WS without migrations. A previous known hardness result suits only the case of one channel when the gap between consecutive schedules of request i must be exactly wi . The offline WS problem has polynomial time algorithm [4] that uses H ( ) + O(ln(H ( )) channels. By contrast, in Section 3, we show the any-fit decreasing is a polynomial time algorithm for off-line UFBP that uses H ( ) + 1 bins. So it appears that UFBP is "easier" than WS in the off-line setting. In Section 4 we consider on-line algorithms for UFBP. We first show that for any value h0 there exists a sequence of requests with H ( ) h0 such that any on-line UFBP algorithm requires H ( ) + (ln(H ( ))) bins. This demonstrates that the on-line UFBP problem is "harder" than the offline problem. Next, we give a tight analysis of the natural algorithms next-fit and any-fit. Finally, we give a polynomial time algorithm that uses H ( ) + H O( ( )) bins. in Section 5 we consider on-line algorithms for WS. First, we give a non-trivial algorithm that uses 226 Lower Bound Off-line On-line H ( ) H ( ) + (ln(H ( ))) [ ] UFBP upper bound H ( ) +(1 [ ] H ( ) + O( H ( ))) [ ] WS upper bound H ( ) + O(ln(H ( ))) [4] ( H ( ) + O( H ( ))) [ ] Table 1: Results for UFBP and WS in the off-line and the on-line settings. the optimal number of channels H ( ) when the windows form a divisible sequence (the equivalent problem for UFBP has a simpler greedy optimal algorithm [8]). Then, for general instances, wH give e an on-line algorithm that uses H ( ) + O( ( )) channels. We emphasize that although this bound is the same as for on-line UFBP, the WS algorithm is substantially more complicated. Table 1 summarizes the results for UFBP and WS in the off-line and on-line settings. Our results are marked with [ ]. Due to space limitations some of the proofs are omitted and some are sketched. 2 NP-hardness ists. Otherwise, the current item is packed in a new opened bin. We are not specific about which bin to pack an item because our analysis suits any bin selection (e.g, first-fit or best-fit). Theorem 3.1. For any sequence , NAFD ( ) H ( ) + 1. Proof. After being sorted in a non-increasing order, the input sequence has the form f = 1 n2 , 1 n3 ,..., 1 nw 2 3 w We show that window scheduling without migration is NP-hard. That is, the problem is NP-Hard when broadcasts of a page have to be from the same channel. We do not know if the problem is still NP-hard when migration is permitted. A previous hardness proof for WS ([3]) works only for a single channel for the restricted case where all the gaps between two consecutive appearances of request i must be exactly wi . Our proof is simpler, holds for arbitrary number of channels, and covers the case in which gaps between schedules of request i may vary. Theorem 2.1. Windows scheduling without migration is NP-hard. 2 For the UFBP problem, migration makes the problem trivial since it means that items can split among several bins. In this case, the greedy packing is clearly optimal. However, without splits, we only know that it is NP-hard if the size of a bin is 1/k for arbitrary k . 3 Off-line UFBP or some integers w 2 and ni 0 for 2 i w. Assume that AFD uses h ful l bins (filled to capacity 1) and h non-ful l bins. Thus, NAFD ( ) = h + h . Claim 3.1. After packing al l the items of width at least 1/k , there are at most k - 1 non-ful l bins. Proof. The proof is by induction on k . The base case is k = 2. Clearly, the items of width 1/2 are packed in n2 /2 bins, where only the last one might be nonfull. Assume that the claim holds before packing the items of width 1/k . That is, after packing the items of width at least 1/(k - 1), there are at most k - 2 non-full bins. Since items of size 1/k are first added to currently non-full bins that can accommodate them, it follows that only one bin that contains only items of size 1/k might be non-full after all the 1/k items are packed. 2 Suppose the last bin that AFD opened was opened for an item of width 1/w where w w. By Claim 3.1, at this stage, there are less than w nonfull bins. Since this is the last opened bin, it follows that h < w . Furthermore, each of the first h - 1 non-full bins must contain items whose total width is greater than 1 - (1/w ), because otherwise AFD would not open a new bin for 1/w . By definition, the last non-full bin contains one item of width 1/w . It follows that We present a polynomial time algorithm for UFBP which is optimal up to an additive term of 1. Any Fit Decreasing (AFD): The items are processed in a non-increasing order of their widths. The current item is packed in any bin it fits if such ex- 227 decreasing sequence of the type H() h + (h = 1 1 w +w h -2 h+h h+h -1- w> - 1) 1 - - f 2. w 1 xw , w-1 1 x w -1 ,..., 1 x2 2 h + Since H ( ) is an integer, it must be at least h - 1. Thus, NAFD ( ) = h + h H ( ) + 1. 2 Since H ( ) NOPTB ( ), it follows that NAFD ( ) NOPTB ( ) + 1. The above analysis is tight, as demonstrated by .the non-increasing se11 1 quence = 2 , 3 , 1 , 4 , 1 , 1 The optimal solution 3 44 a 1 nd the uses two bins, the first c. ntains 2 , 1 , 1 o 44 111 second contains 3 , 3 , 4 On the other hand, AFD packs the first two items in one bin, the next three items in another bin, and then it is forced to pack the last item of width 1/4 in a third bin since the available free space in each of the first two bins is 1/6. Hence, NAFD ( ) NOPTB ( ) + 1. The above theorem gives a clear distinction between BP and UFBP. This is because in BP, NOPT ( ) can be arbitrarily close to 2H ( ) (when consists of items of width 1/2 + ). 4 On-line UFBP or integers xi 0 for 2 i w. The adversary sets the values of xw , xw-1 , . . . , x2 as follows. Let 2 i w and assume xw , . . . , xi+1 have been already set. The adversary requests items of width 1/i until one of the following two conditions holds for the bins used by Algorithm B : 1. There is a bin containing exactly i - 1 items of width 1/i and no other items. 2. There are at least ih0 bins which are filled only with items of width 1/i but no more than i - 2 such items. Note that if xi is large enough then one of the two conditions must hold (for i = 2 the first condition must hold). If the first condition holds and i > 2, then the adversary starts requesting items of width 1/(i - 1). If the second condition holds the adversary stops (formally, it sets xi-1 = · · · = x3 = x2 = 0). The Theorem is proved using the following claims. Claim 4.1. H ( ) h0 . 2 In this section we address the on-line UFBP problem. We first show a non-trivial lower bound. Next, we analyze "fit" greedy algorithms. Finally, we show a better algorithm that sometimes opens a new bin for an item even if a bin with enough free space to accommodate this item exists. 4.1 An H ( ) + (ln H ( )) Lower Bound for On-line UFBP. We prove that no on-line algorithm for UFBP can guarantee a solution with H ( ) + o(ln(H ( ))) bins for any sequence . Since there exists an upper bound of H ( ) + 1 for the offline UFBP, this result shows a significant gap between what can be achieved off-line and what can be achieved on-line for UFBP. Theorem 4.1. For any on-line algorithm B for UFBP and for any integer h0 > 0, there exists a sequence such that H ( ) h0 and NB ( ) = H ( ) + (ln(H ( ))). Proof. Let w be the smallest integer such that w i=2 1/i h0 . It follows that h0 = (ln w ) . We describe an adversary strategy that constructs a non- Claim 4.2. The total free space in al l of the bins of B is at least (ln(w)). 2 Claim 4.3. NB ( ) < w2 ln(w). 2 Consequently, for this sequence, the total item width is at most NB ( ) - (ln(w)) w 2 ln(w) - (ln(w)), and thus, H ( ) w 2 ln(w) - (ln(w)). Since ln(NB ( )) ln(w2 ln(w)) = (ln(w)), it follows that NB ( ) H ( ) + (ln(H ( ))). 2 By Theorem 3.1, NOPTB ( ) H ( ) + 1. Combined with the above, we have Corollary 4.1. For any on-line algorithm B for UFBP and for any constant h0 , there exists a sequence such that H ( ) h0 and NB ( ) = NOPTB ( ) + (ln(NOPTB ( ))). 4.2 Any-fit and Next-Fit. In this section we consider simple on-line algorithms for UFBP. In particular, we analyze the performance of the Nextfit and the Any-fit algorithms defined as follows: 228 Next Fit (NF): An item is packed in the last opened bin if this bin has enough free space for it. Otherwise, a new bin is opened. Any Fit (AF): An item is packed in any one of the bins that has enough free space for it. In fact, Any fit is a class of algorithms, differ by the way the actual bin in which the item is packed is selected. In First-fit the item is packed in the first bin that has enough free space for its width. Other Any-fit algorithms might prefer the ful lest or the emptiest bin that can accommodate the new item. Our analysis shows that for the UFBP problem all AF algorithms have the same worst-case performance regardless of the selection rule. The following results state the exact competitive ratios of NF and AF. That is, for A {NF, AF}, (i) for any sequence , NA ( ) (A)NOPTB ( ), and, (ii) for any n there exists a sequence of size (n) for which NA ( ) = (A)NOPTB ( ). Theorem 4.2. (NF) = 2. 6 Theorem 4.3. (AF) = 5 . fit" type algorithms. In order to get a better result, we develop algorithms that sometimes open a new bin for an item even if this item fits into one of the previously opened bins. Definition 4.1. A bin is i-dedicated if only items of size 1/i are packed in it. We define a set of on-line algorithms {Bk } for k = 1, 2, . . . such that for any sequence , NBk ( ) k+1 k H ( ) + k . Algorithm B1 is the first-fit algorithm. Algorithm B2 dedicates bins to items of width 1/2 and packs all other items according to first-fit rule. That is, an item of width 1/2 is either packed in an open 2-dedicated bin or in a new 2-dedicated bin and any item with a smaller width is packed in the first non-dedicated bin that can accommodate it. In general, Algorithm Bk dedicates bins to items of width 1/2, 1/3, . . . , 1/k and packs all the items with smaller width according to first-fit rule. That is, an item of width 1/j , for 2 j k , is either packed in an open j -dedicated bin or in a new j -dedicated bin and any item with a smaller width is packed in the first non-dedicated bin that can accommodate it. 2 Proof. We first show (AF) 6 . Consider the 5 following sequence of 12x item width for x 1: 11 1111 , , , ,..., , . 2323 23 Lemma 4.1. For any sequence and k > 0, NBk ( ) k+1 H ( ) + k . k Proof. For all j = 2, . . . , k , all j -dedicated bins, exAn optimal solution packs all the items with width cept maybe for the last one, are full (each containing 1/2 in 3x bins and all the items with width 1/3 in j items of size 1/j ). Thus, there are at most k - 1 2x bins for a total of 5x bins. AF allocates a bin non-full dedicated bins. The other bins are filled acfor any pair of adjacent items one of width 1/2 and cording to first-fit rule with items whose width is at one of width 1/3 for a total of 6x bins. Thus, the most 1/(k + 1). Hence, a new non-dedicated bin is 6x competitive ratio of AF is at least 5x = 6 . For the opened only if all previously opened non-dedicated 5 upper bound, assume that there exists a sequence bins are at least k /(k + 1)-full. Thus, all the non of items for which (AF) > (6/5). Then there dedicated bins except maybe for the last one are at exists a bin whose capacity is less than 5/6 and a least k /(k + 1)-full. Adding the last non-dedicated point in the sequence after which the width of any bin to the k - 1 non-full dedicated bins, we get that item is greater than 1/6. That is, after this point, a there are at most k bins whose capacity could be width could have only the values: 1/2, 1/3, 1/4, 1/5. small, and the total number of bins used is i + Since no linear combination of these 4 values totals k+1 k+1 k 1/wi H ( ) + k . a value that is less than 5/6 and greater than 4/5, NBk ( ) k k it follows that there is no additional bin whose capacity is less than 5/6. Therefore, AF allocates at 2 H most (6/5)H (S ) + 1 bins to the sequence . Thus, ( ). For simplicity, we assume Let h = for any > 0 and for any long enough sequences that h is an integer. Otherwise, we round h to 6 (AF) 5 + . 2 the nearest integer, the analysis is similar. Assume first that H ( ) is known in advance. The expression H 4.3 An H ( ) + O( ( )) algorithm. The pre- k+1 H ( ) + k is minimized for k = h. The following k vious section demonstrated the limitation of "must lemma gives the bound for Bh . 229 Lemma 4.2. For any sequence , NBh ( ) H ( ) + 2 H ( ). form the building blocks of our concluding algo rithm, Wdyn that has the same performance as Al gorithm Bdyn for UFBP. 5.1 An Optimal Algorithm for Powers of 2 Windows. Assume that the sequence contains only windows that are powers of 2. That is, wi = 2vi for an integer vi 1 for 1 i n. A B C D When H ( ) is not known in advance, we dynamically increase the parameter k for which dedicated bins exist for 1/2, 1/3, . . . , 1/k . Algorithm Bdyn is defined as follows: Let H denote the total width of the already packed items. As long as H 1, use B1 (regular first-fit), when 1 < H 4, shift to B2 , and in general, when (k - 1)2 < H k 2 , use Algorithm Bk . Note that when Bdyn shifts to Algorithm Bk , it continues to use the bins that were used for Bk-1 , it just adds a new (initially empty) k -dedicated bin. Theorem 4.4. For any sequence , H NBdyn ( ) H ( ) + 4 ( ). Figure 1: Tree representation of the cyclic schedule [A, B , A, C, A, B , A, D]. We represent each channel schedule by a binary tree, in which all the internal nodes have degree 2. The tree leaves represent the scheduled items. To construct the schedule from a tree, alternate between scheduling an item from the left and the right subtrees. The item selected from each subtree is selected by alternating recursively between the left and right subtree in each subtree. For example, the tree in Figure 1 represents a schedule that alternates between 'A' (the only item in the left subtree) and an item from the right subtree. In selecting this right-subtree item, the schedule alternates between 'B' and an item from the right subtree, and so on. It follows that a leaf, , whose depth in the tree is d( ) represents an item scheduled with window size 2d( ). The whole schedule is represented by a forest of binary trees, each representing one channel. We denote by open a leaf that is not assigned yet to any request, and by active a tree that is not fully utilized yet, that is, a tree with at least one open leaf, representing a channel schedule with idle slots. Let the label of a leaf of depth d( ) be 2d( ) . Definition 5.1. A lace binary tree of height h is a binary tree of height h in which there is a single leaf in each of the depths 1, 2, . . . , h - 1, and two leaves in depth h. For example, the tree in Figure 1 is a lace binary tree of height 3. Proof. Let sk denote the subset of of items that were packed while executing Bk . It follows that the total width of items in s1 is less than 1 + 1 , the total 2 width of items in s2 is less than 22 + 1 - 12 = 3, 2 and in general, the total size of items in sk is less 1 than k 2 + 1 - (k - 1)2 < 2k . The additive term 2 2 1 exists since there might be an overflow of 2 beyond (k - 1)2 before the algorithm shifts to Bk . As in the proof of Lemma 4.1, it follows that while Bk is executed, the algorithm opens a new bin only if all the current opened bins (including nondedicated bins that have been opened during the execution of Bk-1 ) are at least k /(k + 1)-full. In addition, during the execution of Bk , there might be at most k - 1 non-full dedicated bins and only one non-dedicated bin with small capacity (the last one). H Recall that h = ( ). Thus, Bh is the last algorithm executed by Bdyn . The total number of bins used by Bdyn is at most h+ kh k + 1 i kh k + 1 1 0. Let d denote on one of the two leaves with depth vi + 1 in T . the maximum depth of any active tree. Then the The proof of the next lemma is a generalization total bandwidth of the open leaves in all the first h of the proof of Lemma 5.2. d opened trees is at most j =1 1/2vi +j which is less Lemma 5.3. For any sequence in which for al l than 1/2vi . Therefore, the total bandwidth required i, wi = c2vi we have NWc ( ) = H ( ). 2 by the new 1/2vi request and the requests already scheduled is more than h. 2 H 5.3 An H ( ) + O( ( )) Algorithm for Arbi5.2 An Optimal Algorithm for Windows of trary Windows. For arbitrary windows, we define the form c2vi . We generalize algorithm W1 to work a parameterized family of on-line algorithms Wk for k+1 for instances in which there exists an integer c such k = 1, 2, . . . such that NWk ( ) k H ( ) + k for vi that all the wi 's are of the form c2 for an integer any request sequence . 231 Algorithm W1 : Let wi be the window of the next request to be scheduled. Round down wi to the nearest power of 2 and apply algorithm W1 on the resulting request. Algorithm Wk : Maintain k sets of channels: C1 , . . . , Ck . On the channel-set Cj , schedule requests whose window is rounded down to (2j - 1)2vi . Let wi be the window of the next request to be scheduled. Round down wi to the nearest number of the form c2vi where c {1, 3, . . . , 2k - 1} and use algorithm Wc to schedule the rounded request on C c+1 . 2 use W1 . That is, all the windows are rounded down to the closest power of 2. When 1 < H 4, shift to W2 . That is, the windows are rounded down to the closest number of the form either 2vi or 3 · 2vj . In general, when (k - 1)2 < H k 2 , use algorithm Wk . That is, a window wi is rounded down to the closest number of the form c2vi where c {1, 3, . . . , 2k - 1}, Note that when the algorithm shifts to Algorithm Wk , it continues to use the channel-sets that were used for Wk-1 , it just adds a new (initially empty) channel-set Ck . Lemma 5.4. For any sequence and k > 0, NWk ( ) k+1 H ( ) + k . k Proof. We first show that when Algorithm Wk is applied, a request with window w is rounded to a request with window w such that w is "close" to w. Then we analyze the performance of Wk on the rounded windows. Claim 5.1. For any integer w and any k 0, there w exists an integer w < w such that (i) w k+1 , k and (ii) c {1, 3, . . . , 2k - 1} and v such that w = c2v . 2 Let wi denote the rounded window of request i. Let denote the sequence of the rounded windows, and let c denote the subset of of the requests whose windows are rounded to c2v for some integer v 0i By Lemma 5.3, Algorithms Wc uses . i c i i H ( ) = 1+ c 1/w c 1/w channels to schedule all the requests in c . Summing over all the k channel-sets, we get that all the requests i i are scheduled on at most 1/w + k channels. i i k+1 i By Claim 5.1 1/wi . Thus, 1/w k k 2 NWk ( ) k+1 H ( ) + k . H Let h = ( ). Assume first that H ( ) is known in advance. The expression k+1 H ( ) + k is k minimized for k = h. The following lemma gives the bound for Wh . Lemma 5.5. For any sequence , NWh ( ) H ( ) + 2 H ( ). That is, Algorithm Proof. Recall that h = Wh is the last algorithm executed by Wdyn . Let di w denote the rounded window of request i. Let enote the sequence of the rounded windows. As in the proof of Lemma 5.4, we have that Wdyn uses at i i most h + 1/w channels. We now b ound the bandwidth lost due to rounding. The idea is that, indeed, prefixes of has a smaller range of rounding possibilities, however, this loss is proportional to the total bandwidth request of the prefix. In particular, the bulk of the requests has all the h rounding possibilities . Let sc denote the subset of of requests arriving while executing Wc . As in the proof of Theorem 4.4, we have that the total bandwidth request of sk is at most 2k . By Claim 5.1, when executing Wk , we k i round the requests such that w k+1 wi . Thus, i 1 wi = i k+1 1 k+1i = k wi k s wi k Theorem 5.1. For any sequence , H ( ). NWdyn ( ) H ( ) + 4 sk sk k+1 (2k ) = 2(k + 1). k Therefore, the total number of channels used by Wdyn is at most h+ i wi 1 = h+ When H ( ) is not known in advance, we dynamically increase the number of channel-sets (the parameter k ). Algorithm Wdyn is defined as follows: d Let H enote the total bandwidth requirement of the already scheduled requests. As long as H 1, H kh 2(k + 1) = h2 + 4h = H + 4 H 2 =1 ( ). 6 Op en Problems In this paper we addressed the Unit Fractions Bin Packing (UFBP) problem and the Windows Scheduling (WS) problem in the off-line and the on-line settings. A summary of the results can be found in 232 Table 1 in Section 1.3. The following problems remain open. 1. For off-line UFBP, we know a solution which is optimal up to an additive term of 1. Is this problem NP-hard? 2. Is there an off-line algorithm for WS that outperforms the solution of [4]? Also, does there exist a non-trivial lower bound, larger than H ( ) + 1, for the off-line WS problem that separates it from the off-line UFBP problem? 3. The upper bounds for on-line UFBP and WS are the same. Is there a better upper bound for on-line UFBP as is the case in the off-line setting? 4. The only lower bound we have for on-line WS is the one for UFBP. Is there a larger lower bound for on-line WS, one that takes advantage of the additional restriction imposed by the WS problem? 5. All of our algorithm for WS do not migrate requests from channel to another channel. Can migration help in the off-line or the on-line setting? Furthermore, if migration is permitted, is WS an NP-Hard problem? References [1] S. Acharya, M. J. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. IEEE Personal Comm., 2(6):50­60, 1995. [2] M. H. Ammar and J. W. Wong. The design of teletext broadcast cycles. Performance Evaluation, 5(4):235­242, 1985. [3] A. Bar-Noy, R. Bhatia, J. Naor, and B. Schieber. Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research (MOR), 27(3):518­544, 2002. [4] A. Bar-Noy and R. E. Ladner. Windows scheduling problems for broadcast systems. In Proc. of the 13-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 433­442, 2002. [5] A. Bar-Noy, R. E. Ladner, and T. Tamir. Scheduling techniques for media-on-demand. In Proc. of the 14-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 791­800, 2002. [6] A. Bar-Noy, J. Naor, and B. Schieber. Pushing dependent data in clients-providers-servers systems. Wireless Networks journal, 9(5):175­186, 2003. [7] E. G. Coffman, C .A. Courcoubetis, M .R. Garey, D .S. Johnson, P .W. Shor, R .R. Weber, and M. Yannakakis. Bin packing with discrete item sizes, part I: perfect packing theorems and the average case behavior of optimal packings. SIAM J. Discrete Math., 13:384­402, 2000. [8] E. G. Coffman, M .R. Garey, and D .S. Johnson. Bin packing with divisible item sizes. J. of Complexity, 3:406­428, 1987. [9] E. G. Coffman, M .R. Garey, and D .S. Johnson. Approximation Algorithms for Bin Packing: A Survey. Approximation Algorithms for NP-Hard Problems, D. Hochbaum (editor), PWS Publishing, Boston (1996), 46­93. [10] L. Engebretsen and M. Sudan. Harmonic broadcasting is optimal. In Proc. of the 13-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 431­432, 2002. [11] M .R. Garey and D .S. Johnson. Computers and intractability: a guide to the theory of NPcompleteness. W.H. Freeman, 1979. [12] V. Gondhalekar, R. Jain, and J. Werth. Scheduling on airdisks: efficient access to personalized information services via periodic wireless data broadcast. IEEE International Conference on Communications (ICC), 3:1276­1280, 1997. [13] K. A. Hua and S. Sheu. An Efficient Periodic Broadcast Technique for Digital Video Libraries. Multimedia Tools and Applications, 10(2/3):157­ 177, 2000. [14] D .S. Johnson, A. Demers, J .D. Ullman, M .R. Garey, and R.L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithm. SIAM J. of Comput., 3:256­278, 1974. [15] L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 43(3):268­271, 1997. [16] V. Kann. Maximum bounded 3-dimensional matching is max SNP-complete. Information Processing Letters, 37:27­35, 1991. [17] C. L. Liu and W. Laylend. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46­61, 1973. [18] S. Seiden. On the online bin-packing problem. Journal of the ACM, 49(5):640-671, 2002. [19] R. Tijdeman. The chairman assignment problem. Discrete Mathematics, 32:323­330, 1980. [20] A. van Vliet. On the asymptotic worst case behavior of harmonic fit. J. of Algs., 20:113­136, 1996. [21] W .F. Vega and G .S. Leuker. Bin packing can be solved within 1 + in linear time. Combinatorica, 1:349­355, 1981. [22] S. Viswanathan and T. Imielinski. Metropolitan area video-on-demand service using pyramid broadcasting. ACM Multimedia Systems Journal, 4(3):197­208, 1996. 233