A primal-dual randomized algorithm for weighted paging

N. Bansal, N. Buchbinder, J. Naor

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    36 Citations (Scopus)


    In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized {\rm O}(\log k)-competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitiveness matches the known lower bound on the problem. More generally, we design an {\rm O}(\log (k/(k - h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and the offline algorithm has cache size h \leqslant k. Weighted paging is a special case (weighted star metric) of the well known k-server problem for which it is a major open question whether randomization can be useful in obtaining sublinear competitive algorithms. Therefore, abstracting and extending the insights from paging is a key step in the resolution of the k-server problem. Our solution for the weighted paging problem is based on a two-step approach. In the first step we obtain an {\rm O}(\log k)-competitive fractional algorithm which is based on a novel online primal-dual approach. In the second step we obtain a randomized algorithm by rounding online the fractional solution to an actual distribution on integral cache solutions. We conclude with a randomized {\rm O}(\log N)-competitive algorithm for the well studied Metrical Task System problem (MTS) on a metric defined by a weighted star on N leaves, improving upon a previous {\rm O}(\log ^2 N)-competitive algorithm of Blum et al.
    Original languageEnglish
    Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07, Providence RI, USA, October 20-23, 2007)
    PublisherIEEE Computer Society
    ISBN (Print)0-7695-3010-9
    Publication statusPublished - 2007


    Dive into the research topics of 'A primal-dual randomized algorithm for weighted paging'. Together they form a unique fingerprint.

    Cite this