A primal-dual randomized algorithm for weighted paging

N. Bansal, N. Buchbinder, J. Naor

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    31 Citaten (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.
    Originele taal-2Engels
    TitelProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07, Providence RI, USA, October 20-23, 2007)
    UitgeverijIEEE Computer Society
    ISBN van geprinte versie0-7695-3010-9
    StatusGepubliceerd - 2007


    Duik in de onderzoeksthema's van 'A primal-dual randomized algorithm for weighted paging'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit