Conference item icon

Conference item

Learning-augmented weighted paging

Abstract:

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging [45, 50, 52] to the weighted setting.
For the case of perfect predictions, we provide an ℓ-competitive deterministic and an O(log ℓ)-competitive randomized al...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/1.9781611977073.4

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Anne's College
Role:
Author
ORCID:
0000-0003-3744-0977
Publisher:
Society for Industrial and Applied Mathematics
Host title:
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
Pages:
67-89
Publication date:
2022-01-05
Event title:
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
Event location:
Virginia, USA
Event website:
https://www.siam.org/conferences/cm/conference/soda22
Event start date:
2022-01-09
Event end date:
2022-01-12
DOI:
ISBN:
9781611977073
Language:
English
Keywords:
Pubs id:
1308700
Local pid:
pubs:1308700
Deposit date:
2023-03-28

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP