algorithm design techniques online algorithms the first issue to consider is whether or not an online algorithm can actually always give an optimal answereven if it is allowed unlimited computation remember that even though unlimited computation is allowedan online algorithm must place an item before processing the next item and cannot change its decision to show that an online algorithm cannot always give an optimal solutionwe will give it particularly difficult data to work on consider an input sequencei of small items of weight followed by large items of weight it is clear that these items can be packed in bins if we place one small item and one large item in each bin suppose there were an optimal online algorithmathat could perform this packing consider the operation of algorithm on the sequence consisting of only small items of weight can be packed in  / bins howevera will place each item in separate binsince must yield the same results on as it does for the first half of and the first half of is exactly the same input as this means that will use twice as many bins as is optimal for what we have proved is that there is no optimal algorithm for online bin packing what the argument above shows is that an online algorithm never knows when the input might endso any performance guarantees it provides must hold at every instant throughout the algorithm if we follow the foregoing strategywe can prove the following theorem there are inputs that force any online bin packing algorithm to use at least the optimal number of bins proof suppose otherwiseand suppose for simplicitythat is even consider any online algorithm running on the input sequence above recall that this sequence consists of small items followed by large items let us consider what the algorithm has done after processing the mth item suppose has already used bins at this point in the algorithmthe optimal number of bins is / because we can place two elements in each bin thus we know that / by our assumption of better-than performance guarantee now consider the performance of algorithm after all items have been packed all bins created after the bth bin must contain exactly one itemsince all small items are placed in the first binsand two large items will not fit in bin since the first bins can have at most two items eachand the remaining bins have one item eachwe see that packing items will require at least bins since the items can be optimally packed using binsour performance guarantee assures us that ( )/ the first inequality implies that / and the second inequality implies that / which is contradiction thusno online algorithm can guarantee that it will produce packing with less than the optimal number of bins there are three simple algorithms that guarantee that the number of bins used is no more than twice optimal there are also quite few more complicated algorithms with better guarantees