Weighted k-server bounds via combinatorial dichotomies

N. Bansal, M. Elias, G. Koumoutsos

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)

Samenvatting

The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.
Originele taal-2Engels
Titel2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California
Plaats van productiePiscataway
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's493-504
Aantal pagina's12
ISBN van elektronische versie978-1-5386-3464-6
ISBN van geprinte versie978-1-5386-3465-3
DOI's
StatusGepubliceerd - 2017
Evenement58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California - DoubleTree Hotel at the Berkeley Marina, Berkeley, Verenigde Staten van Amerika
Duur: 15 okt. 201717 okt. 2017
https://focs17.simons.berkeley.edu/

Congres

Congres58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California
Verkorte titelFOCS 2017
Land/RegioVerenigde Staten van Amerika
StadBerkeley
Periode15/10/1717/10/17
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Weighted k-server bounds via combinatorial dichotomies'. Samen vormen ze een unieke vingerafdruk.

Citeer dit