Double Coverage with Machine-Learned Advice
Date Issued
2022
Abstract
We study the fundamental online k-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (e.g. machine-learned predictions) on an algorithm’s decision. There is, however, no guarantee on the quality of the prediction and it might be far from being correct.
Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k-server on the line (Chrobak et al., SIDMA 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent competitive ratio, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal consistency, the performance in case that all predictions are correct, and the best-possible robustness regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff, within a class of deterministic algorithms respecting local and memoryless properties.
Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is remarkable that the previous algorithm crucially exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.
Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k-server on the line (Chrobak et al., SIDMA 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent competitive ratio, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal consistency, the performance in case that all predictions are correct, and the best-possible robustness regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff, within a class of deterministic algorithms respecting local and memoryless properties.
Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is remarkable that the previous algorithm crucially exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.
Subjects
online k-server problem
;
competitive analysis
;
learning-augmented algorithms
;
untrusted predictions
;
consistency
;
robustness
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Institution
Type
conference paper
Journal/Edited collection
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) = Leibniz International Proceedings in Informatics (LIPIcs), Band 215
Start page
99:1
End page
99:18
Secondary publication
Yes
Document version
Published Version
Language
English
File(s)![Thumbnail Image]()
Loading...
Name
Lindermayr_Megow_Simon_Double Coverage with Machine-Learned Advice_2022_published-version.pdf
Size
1.17 MB
Format
Adobe PDF
Checksum
(MD5):79eab500cf94cd9df14183afffa25486