Efficient Online Weighted Multi-Level Paging
Nikhil Bansal, Joseph Seffi Naor, Ohad Talmon · 2021
We study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(łog^2 k) competitive randomized algorithm, answering an open question of Beckmann ηl~BGHM20 and Even et al. (21) about the existence of a randomized poly-logarithmic competitive algorithm. Our algorithm also works for arbitrary page weights. We also give an O(k) competitive deterministic algorithm, extending the previous result of Beckmann et al. BGHM20 to the weighted setting.