What To Do With Your Free Time: Algorithms for Infrequent Requests and Randomized Weighted Caching

We consider an extension of the standard on-line model to settings in which an on-line algorithm has free time between successive requests in an input sequence. During this free time, the algorithm may perform operations without charge before receiving the next request. For instance, in planning the motion of fire trucks, there may be time in between fires that one could use to reposition the trucks in anticipation of the next fire. We prove both upper and lower bounds on the power of deterministic and randomized algorithms in this model. As our main lemma, we show an O(log 2 k)-competitive algorithm and an\Omega\Gamma/44 k) lower bound on the competitive ratio for any weighted caching problem on (k + 1)-point spaces in the standard on-line model, thus making progress on an open problem of [MMS88b, You91]. These results also apply to any metrical task system on spaces corresponding to weighted star graphs. We also consider extensions to the standard on-line model in which both free t..