The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize th
e total size of all the bins used. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For these item sizes and maximum bin size 4S-3, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance me
asures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.
Though competitive analysis has been a very useful performance measure for the quality of online algorithms, it is recognized that it sometimes fails to distinguish between algorithms of different quality in practice. A number of alternative measures
have been proposed, but, with a few exceptions, these have generally been applied only to the online problem they were developed in connection with. Recently, a systematic study of performance measures for online algorithms was initiated [Boyar, Irani, Larsen: Eleventh International Algorithms and Data Structures Symposium 2009], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, Random Order, and Max/Max. In addition to drawing conclusions on this work, we also investigate the measures sensitivity to integral vs. real-valued domains, and as a part of this work, generalize some of the known performance measures. Finally, we have established the first optimality proof for Relative Interval Analysis.
