License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.9
URN: urn:nbn:de:0030-drops-161693
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16169/
Go to the corresponding LIPIcs Volume Portal

Antoniadis, Antonios ; Jabbarzade, Peyman ; Shahkarami, Golnoosh

A Novel Prediction Setup for Online Speed-Scaling

pdf-format:
LIPIcs-SWAT-2022-9.pdf (0.8 MB)

Abstract

Given the rapid rise in energy demand by data centers and computing systems in general, it is fundamental to incorporate energy considerations when designing (scheduling) algorithms. Machine learning can be a useful approach in practice by predicting the future load of the system based on, for example, historical data. However, the effectiveness of such an approach highly depends on the quality of the predictions and can be quite far from optimal when predictions are sub-par. On the other hand, while providing a worst-case guarantee, classical online algorithms can be pessimistic for large classes of inputs arising in practice.
This paper, in the spirit of the new area of machine learning augmented algorithms, attempts to obtain the best of both worlds for the classical, deadline based, online speed-scaling problem: Based on the introduction of a novel prediction setup, we develop algorithms that (i) obtain provably low energy-consumption in the presence of adequate predictions, and (ii) are robust against inadequate predictions, and (iii) are smooth, i.e., their performance gradually degrades as the prediction error increases.

BibTeX - Entry

@InProceedings{antoniadis_et_al:LIPIcs.SWAT.2022.9,
  author =	{Antoniadis, Antonios and Jabbarzade, Peyman and Shahkarami, Golnoosh},
  title =	{{A Novel Prediction Setup for Online Speed-Scaling}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16169},
  URN =		{urn:nbn:de:0030-drops-161693},
  doi =		{10.4230/LIPIcs.SWAT.2022.9},
  annote =	{Keywords: learning augmented algorithms, speed-scaling, energy-efficiency, scheduling theory, online algorithms}
}

Keywords: learning augmented algorithms, speed-scaling, energy-efficiency, scheduling theory, online algorithms
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI