Online Algorithms with Predictions

Magnus Berg Møhring

doi:10.21996/2952cc68-3caf-449a-aa5b-df286316b63e

Online Algorithms with Predictions

Magnus Berg Møhring

Publikation: Afhandling › Ph.d.-afhandling

20 Downloads (Pure)

Abstract

I denne afhandling undersøger vi det relativt nye, men hurtigt voksende forskningsområde: online-algoritmer med forudsigelser. Den centrale idé bag online-algoritmer medforudsigelser er at give online-algoritmer adgang til (maskinlærte) forudsigelser, der indeholder information om den instans, en algoritme er ved at løse. Målet er, at algoritmerne med forudsigelser klarer sig bedre end algoritmer uden forudsigelser, når forudsigelserne er korrekte, samtidig med at de ikke klarer sig meget dårligere end algoritmer uden forudsigelser, når forudsigelserne er fejlbehæftede. Vi udvikler algoritmer til Online Minimum Spanning Trees with Weight Predictions, Online Bin Covering with Frequency Predictions og Online Dual Bin Packing with Predictions. I øvrigt udvikler vi en kompleksitetsteori med henblik på at klassificere online-problemer med binære forudsigelser baseret på deres indbyrdes sværhedsgrad.

Til Online Minimum Spanning Trees udvikler vi to algoritmer, der er bedst mulige medhensyn til kompetitiv analyse, men hvor den ene intuitivt er bedre end den anden. Vi adskiller de to algoritmer ved hjælp af en “random-order”-analyse.

Til Online Bin Covering beviser vi, at der eksisterer en familie af algoritmer, som er næsten optimale, når forudsigelserne er perfekte. Herefter bygger vi, ved hjælp af kendte resultater fra teorien om maskinlæring, en algoritme uden forudsigelser, der med storsandsynlighed er næsten optimal i gennemsnitstilfælde.

Til Online Dual Bin Packing udvikler vi algoritmer med forudsigelser baseret på en asymptotisk optimal algoritme uden forudsigelser. Vi viser eksistensen af en 12-konsistent online-algoritme med forudsigelser og bruger den til at definere en familie af robuste online-algoritmer med forudsigelser, der er parametriseret ved ens tillid til forudsigelserne. Når tilliden til forudsigelserne ændres, ændres de algoritmiske garantier også.

Endeligt udvikler vi kompleksitetsklasser, der lader os sammenligne sværhedsgraden af online-problemer med binære forudsigelser. Vores bidrag omfatter både definitionen af kompleksitetsklasserne og etableringen af reduktioner, der beviser, at flere bådeminimerings- og maksimeringsproblemer er indeholdt i kompleksitetsklasserne, nogle er svære, og nogle er fuldstændige. Disse resultater beviser dermed også den relative sværhedsgrad af problemerne. Ydermere bruger vi kompleksitetsklassernes struktur til at generalisere negative resultater for Paging with Discard Predictions til andre problemer, som Online Bounded Degree Vertex Cover with Predictions, Online Bounded Degree Independent Set with Predictions, Online Interval Scheduling with Predictions, med flere.

Udover projekter inden for online-algoritmer med forudsigelser indeholder denne afhandling også en artikel, der omhandler datastrukturer. I den artikel udvikler vi en kompaktdatastruktur for “polymonioes” og en succinct datastruktur for “bar graphs”, der understøtter navigations- og sigtbarhedsforespørgsler i konstant tid.

Originalsprog	Engelsk
Bevilgende institution	Syddansk Universitet
Vejledere/rådgivere	Larsen, Kim Skak, Hovedvejleder Favrholdt, Lene Monrad, Vejleder Kandemir, Melih, Vejleder
Dato for forsvar	14. nov. 2025
Udgiver	Syddansk Universitet. Det Naturvidenskabelige Fakultet
DOI	https://doi.org/10.21996/2952cc68-3caf-449a-aa5b-df286316b63e
Status	Udgivet - 4. nov. 2025

Dokumenter og links

10.21996/2952cc68-3caf-449a-aa5b-df286316b63eLicens: Kun læseadgang

Open Access VersionForlagets udgivne version, 1,91 MBLicens: Kun læseadgang

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
Berg, M., 2025, Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. Chau, V., Dürr, C., Li, M. & Lu, P. (red.). Springer Science+Business Media, s. 33-48 (Lecture Notes in Computer Science, Bind 15828 LNCS).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review
Complexity Classes for Online Problems with and Without Predictions
Berg, M., Boyar, J., Favrholdt, L. M. & Larsen, K. S., 2025, Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. Chau, V., Dürr, C., Li, M. & Lu, P. (red.). Springer Science+Business Media, s. 49-63 15 s. (Lecture Notes in Computer Science, Bind 15828 LNCS).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review
Online Bin Covering with Frequency Predictions
Berg, M. & Kamali, S., jun. 2024, 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. Bodlaender, H. L. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 17 s. 10. (Leibniz International Proceedings in Informatics, Bind 294).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Åben adgang
Fil
17 Downloads (Pure)

Citationsformater

@misc{2952cc683caf449aaa5bdf286316b63e,

title = "Online Algorithms with Predictions",

abstract = "In this thesis, we explore the relatively new, but rapidly growing field of online algorithms with predictions. The central idea is to endow online algorithms with a (machine learned) predictor that provides some information about the instance the online algorithm is currently solving. The aim is that algorithms with predictions should outperform algorithms without predictions when the predictions are reliable, while not performing much worse than algorithms without predictions when the predictions are erroneous. We develop algorithms for Online Minimum Spanning Trees with Weight Predictions, Online Bin Covering with Frequency Predictions, and Online Dual Bin Packing with Predictions. Further, we develop a complexity framework that allows for comparing the hardness of online problems with binary predictions. For Online Minimum Spanning Trees, we develop two algorithms that are both optimal in competitive analysis, but where one intuitively outperforms the other. We obtain an algorithmic separation through random-order analysis. For Online Bin Covering, we prove the existence of a family of algorithms that perform near-optimally when the predictions are perfect. Using this, together with a known result from the theory of machine learning, we develop a purely online algorithm that performs near-optimally with arbitrarily high probability in the average case. For Online Dual Bin Packing, we develop algorithms with predictions based on an asymptotically best possible purely online algorithm. We show the existence of an 12-consistentonline algorithm with predictions and give a strategy for robustifying this algorithm into a family of algorithms parametrized by one{\textquoteright}s trust in the predictions. Changing the trust level implies changes in the consistency, robustness, and smoothness of the algorithm. Finally, we develop a complexity framework that allows for comparing the hardness of online algorithms with binary predictions. Our main contribution is the establishment of the framework, as well as highlighting its relevance by proving several membership, hardness, and completeness results of both online minimization and online maximization problems, which provide new insight into the relative hardness of online problems. Further, using the tools provided by our complexity framework, we extend strong negative results for Paging with Discard Predictions to negative results for Online Bounded Degree Vertex Cover with Predictions, Online Bounded Degree Independent Set with Predictions, Online Interval Scheduling with Predictions, and others. Beyond projects related to online algorithms with predictions, this thesis also contains a single research paper in data structures. Here, we develop a compact data structure for polyominoes and a succinct data structure for bar graphs that supports neighborhood and visibility queries in constant time.",

author = "M{\o}hring, \{Magnus Berg\}",

year = "2025",

month = nov,

day = "4",

doi = "10.21996/2952cc68-3caf-449a-aa5b-df286316b63e",

language = "English",

publisher = "Syddansk Universitet. Det Naturvidenskabelige Fakultet",

address = "Denmark",

school = "SDU",

}

TY - GEN

T1 - Online Algorithms with Predictions

AU - Møhring, Magnus Berg

PY - 2025/11/4

Y1 - 2025/11/4

N2 - In this thesis, we explore the relatively new, but rapidly growing field of online algorithms with predictions. The central idea is to endow online algorithms with a (machine learned) predictor that provides some information about the instance the online algorithm is currently solving. The aim is that algorithms with predictions should outperform algorithms without predictions when the predictions are reliable, while not performing much worse than algorithms without predictions when the predictions are erroneous. We develop algorithms for Online Minimum Spanning Trees with Weight Predictions, Online Bin Covering with Frequency Predictions, and Online Dual Bin Packing with Predictions. Further, we develop a complexity framework that allows for comparing the hardness of online problems with binary predictions. For Online Minimum Spanning Trees, we develop two algorithms that are both optimal in competitive analysis, but where one intuitively outperforms the other. We obtain an algorithmic separation through random-order analysis. For Online Bin Covering, we prove the existence of a family of algorithms that perform near-optimally when the predictions are perfect. Using this, together with a known result from the theory of machine learning, we develop a purely online algorithm that performs near-optimally with arbitrarily high probability in the average case. For Online Dual Bin Packing, we develop algorithms with predictions based on an asymptotically best possible purely online algorithm. We show the existence of an 12-consistentonline algorithm with predictions and give a strategy for robustifying this algorithm into a family of algorithms parametrized by one’s trust in the predictions. Changing the trust level implies changes in the consistency, robustness, and smoothness of the algorithm. Finally, we develop a complexity framework that allows for comparing the hardness of online algorithms with binary predictions. Our main contribution is the establishment of the framework, as well as highlighting its relevance by proving several membership, hardness, and completeness results of both online minimization and online maximization problems, which provide new insight into the relative hardness of online problems. Further, using the tools provided by our complexity framework, we extend strong negative results for Paging with Discard Predictions to negative results for Online Bounded Degree Vertex Cover with Predictions, Online Bounded Degree Independent Set with Predictions, Online Interval Scheduling with Predictions, and others. Beyond projects related to online algorithms with predictions, this thesis also contains a single research paper in data structures. Here, we develop a compact data structure for polyominoes and a succinct data structure for bar graphs that supports neighborhood and visibility queries in constant time.

AB - In this thesis, we explore the relatively new, but rapidly growing field of online algorithms with predictions. The central idea is to endow online algorithms with a (machine learned) predictor that provides some information about the instance the online algorithm is currently solving. The aim is that algorithms with predictions should outperform algorithms without predictions when the predictions are reliable, while not performing much worse than algorithms without predictions when the predictions are erroneous. We develop algorithms for Online Minimum Spanning Trees with Weight Predictions, Online Bin Covering with Frequency Predictions, and Online Dual Bin Packing with Predictions. Further, we develop a complexity framework that allows for comparing the hardness of online problems with binary predictions. For Online Minimum Spanning Trees, we develop two algorithms that are both optimal in competitive analysis, but where one intuitively outperforms the other. We obtain an algorithmic separation through random-order analysis. For Online Bin Covering, we prove the existence of a family of algorithms that perform near-optimally when the predictions are perfect. Using this, together with a known result from the theory of machine learning, we develop a purely online algorithm that performs near-optimally with arbitrarily high probability in the average case. For Online Dual Bin Packing, we develop algorithms with predictions based on an asymptotically best possible purely online algorithm. We show the existence of an 12-consistentonline algorithm with predictions and give a strategy for robustifying this algorithm into a family of algorithms parametrized by one’s trust in the predictions. Changing the trust level implies changes in the consistency, robustness, and smoothness of the algorithm. Finally, we develop a complexity framework that allows for comparing the hardness of online algorithms with binary predictions. Our main contribution is the establishment of the framework, as well as highlighting its relevance by proving several membership, hardness, and completeness results of both online minimization and online maximization problems, which provide new insight into the relative hardness of online problems. Further, using the tools provided by our complexity framework, we extend strong negative results for Paging with Discard Predictions to negative results for Online Bounded Degree Vertex Cover with Predictions, Online Bounded Degree Independent Set with Predictions, Online Interval Scheduling with Predictions, and others. Beyond projects related to online algorithms with predictions, this thesis also contains a single research paper in data structures. Here, we develop a compact data structure for polyominoes and a succinct data structure for bar graphs that supports neighborhood and visibility queries in constant time.

U2 - 10.21996/2952cc68-3caf-449a-aa5b-df286316b63e

DO - 10.21996/2952cc68-3caf-449a-aa5b-df286316b63e

M3 - Ph.D. thesis

PB - Syddansk Universitet. Det Naturvidenskabelige Fakultet

ER -

Online Algorithms with Predictions

Abstract

Dokumenter og links

SDU link

Fingeraftryk

Relaterede publikationer

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions

Complexity Classes for Online Problems with and Without Predictions

Online Bin Covering with Frequency Predictions

Citationsformater