Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis

Joan Boyar, Sushmita Gupta, Kim S. Larsen

Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst or…