imported>Mountlex: Added more examples of applications with references

2025-12-18T10:01:41Z

Added more examples of applications with references

New page

A '''learning augmented algorithm''' (also called algorithm with predictions) is an [[algorithm]] that can make use of a prediction to improve its performance.<ref name="MitzenmacherVassilvitskii2020">{{cite book | title = Beyond the Worst-Case Analysis of Algorithms | last1 = Mitzenmacher | author-link1 = Michael Mitzenmacher | first1 = Michael | last2 = Vassilvitskii | first2 = Sergei | chapter = Algorithms with Predictions | date = 31 December 2020 | pages = 646–662 | publisher = Cambridge University Press | doi = 10.1017/9781108637435.037 | arxiv=2006.09123 | isbn = 978-1-108-63743-5 }}</ref>
Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter.
This extra parameter often is a prediction of some property of the solution.
This prediction is then used by the algorithm to improve its running time or the quality of its output. The most common application are [[online algorithms]],
where a prediction on the uncertain instance is provided.

== Description ==
A learning augmented algorithm typically takes an input <math>(\mathcal{I}, \mathcal{A})</math>. Here <math>\mathcal{I}</math> is a problem instance and <math>\mathcal{A}</math> is the prediction.
A prediction can be any object. Common are the following types:
* '''Prediction of an optimal solution.''' The prediction gives a solution to the problem or characterizes an optimal solution.
* '''Prediction of the input.''' This is mainly used for [[online problem]]s.
* '''Prediction of algorithmic actions.''' A prediction tailored to a specific algorithm that suggests a specific algorithm execution.

Learning augmented algorithms usually satisfy the following three properties:<ref name="MitzenmacherVassilvitskii2020" />
* '''Consistency.''' A learning augmented algorithm is said to be consistent if the algorithm can be proven to have a good performance when it is provided with an accurate prediction.
* '''Smoothness.''' A learning augmented algorithm is called smooth if its performance can be bounded by a function of the quality of the prediction. Here, the quality can be measured in a problem specific way. This is also called the prediction error.
* '''Robustness.''' A learning augmented algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.

Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose [[machine learning]] can be used.{{fact|date=May 2022}}

== Applications ==

A few examples of problems where learning augmented algorithms have been applied are the following.

=== Online algorithms ===

* The [[ski rental problem]]<ref>{{cite conference
|last1=Purohit
|first1=Manish
|last2=Svitkina
|first2=Zoya
|last3=Kumar
|first3=Ravi
|title=Improving Online Algorithms via ML Predictions
|book-title=Advances in Neural Information Processing Systems 31 (NeurIPS 2018)
|pages=9684–9693
|year=2018
|location=Montréal, Canada
|url=https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html
|access-date=18 December 2025
}}</ref>
* The weighted [[Page replacement algorithm#The (h,k)-paging problem|paging problem]]<ref name="BansalCoesterKumar2022">{{cite book | title = Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | last1 = Bansal | first1 = Nikhil | last2 = Coester | first2 = Christian | last3 = Kumar | first3 = Ravi | last4 = Purohit | first4 = Manish | last5 = Vee | first5 = Erik | chapter = Learning-Augmented Weighted Paging | date = January 2022 | pages = 67–89 | publisher = Society for Industrial and Applied Mathematics | doi = 10.1137/1.9781611977073.4 | arxiv = | isbn = 978-1-61197-707-3 | url = https://ora.ox.ac.uk/objects/uuid:f8f430f4-23fd-49b9-9cf4-1c24230151cf }}</ref>
* The [[set cover problem]]<ref>{{cite conference
|last1=Bamas
|first1=Étienne
|last2=Maggiori
|first2=Andreas
|last3=Svensson
|first3=Ola
|title=The Primal-Dual Method for Learning Augmented Algorithms
|book-title=Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
|year=2020
|location=Virtual conference
|url=https://proceedings.neurips.cc/paper/2020/hash/e834cb114d33f729dbc9c7fb0c6bb607-Abstract.html
|access-date=18 December 2025
}}</ref><ref>{{cite arXiv
|last1=Grigorescu
|first1=Elena
|last2=Lin
|first2=Young-San
|last3=Silwal
|first3=Sandeep
|last4=Song
|first4=Maoyuan
|last5=Zhou
|first5=Samson
|title=Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
|eprint=2209.10614
|class=cs
|year=2022
}}</ref>
* Nonclairvoyant scheduling<ref>{{cite conference
|last1=Im
|first1=Sungjin
|last2=Kumar
|first2=Ravi
|last3=Montazer Qaem
|first3=Mahshid
|last4=Purohit
|first4=Manish
|title=Non-Clairvoyant Scheduling with Predictions
|book-title=Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2021)
|pages=285–294
|publisher=ACM
|year=2021
|location=Virtual conference, USA
|doi=10.1145/3409964.3461790
|url=https://doi.org/10.1145/3409964.3461790
|access-date=18 December 2025
}}</ref><ref>{{cite journal
|last1=Lindermayr
|first1=Alexander
|last2=Megow
|first2=Nicole
|title=Permutation Predictions for Non-Clairvoyant Scheduling
|journal=ACM Transactions on Parallel Computing
|volume=12
|issue=2
|pages=4:1–4:26
|year=2025
|publisher=ACM
|doi=10.1145/3711872
|url=https://doi.org/10.1145/3711872
|access-date=18 December 2025
}}</ref>
* The online [[matching]] problem<ref>{{cite conference
|last1=Jin
|first1=Billy
|last2=Ma
|first2=Will
|title=Online Bipartite Matching with Advice: Tight Robustness–Consistency Tradeoffs for the Two-Stage Model
|book-title=Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
|year=2022
|location=New Orleans, Louisiana, United States
|url=http://papers.nips.cc/paper_files/paper/2022/hash/5d68a3f05ee2aae6a0fb2d94959082a0-Abstract-Conference.html
|access-date=18 December 2025
}}</ref>

=== Warm starting ===

==== Data structures ====
The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>y</math> in a list of length <math>n</math>.
With a prediction <math>i</math> for the position of <math>y</math>, the following learning augmented algorithm can be used.<ref name="MitzenmacherVassilvitskii2020" />

* First, look at position <math>i</math> in the list. If <math>x_i=y</math>, the element has been found.
* If <math>x_i<y</math>, look at positions <math>i+1,i+2,i+4,\ldots</math> until an index <math>j</math> with <math>x_j\geq y</math> is found.
** Now perform a binary search on <math>x_i,\ldots, x_j</math>.
* If <math>x_i>y</math>, do the same as in the previous case, but instead consider <math>i-1,i-2,i-4,\ldots</math>.

The error is defined to be <math>\eta=|i-i^*|</math>, where <math>i^*</math> is the real index of <math>y</math>.
In the learning augmented algorithm, probing the positions <math>i+1,i+2,i+4,\ldots</math> takes <math>\log_2(\eta)</math> steps.
Then a binary search is performed on a list of size at most <math>2\eta</math>, which takes <math>\log_2(\eta)</math> steps. This makes the total running time of the algorithm <math>2\log_2(\eta)</math>.
So, when the error is small, the algorithm is faster than a normal binary search. This shows that the algorithm is consistent.
Even in the worst case, the error will be at most <math>n</math>. Then the algorithm takes at most <math>O(\log(n))</math> steps, so the algorithm is robust.

==== More examples ====

* The [[maximum weight matching]] problem<ref name="neurips_5616060fb8ae85d93f334e7267307664">{{cite book
| first1 = Michael
| last1 = Dinitz
| first2 = Sungjin
| last2 = Im
| first3 = Thomas
| last3 = Lavastida
| first4 = Benjamin
| last4 = Benjamin
| first5 = Sergei
| last5 = Vassilvitskii
| title = Advances in Neural Information Processing Systems
| publisher = Curran Associates, Inc.
| chapter = Faster Matchings via Learned Duals
| url = https://proceedings.neurips.cc/paper/2021/file/5616060fb8ae85d93f334e7267307664-Paper.pdf
| date = 2021
}}</ref>

=== Approximation algorithms ===

* The [[maximum cut]] problem<ref>{{cite conference
|last1=Cohen-Addad
|first1=Vincent
|last2=d'Orsi
|first2=Tommaso
|last3=Gupta
|first3=Anupam
|last4=Lee
|first4=Euiwoong
|last5=Panigrahi
|first5=Debmalya
|title=Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
|book-title=Advances in Neural Information Processing Systems 38 (NeurIPS 2024)
|year=2024
|location=Vancouver, British Columbia, Canada
|url=http://papers.nips.cc/paper_files/paper/2024/hash/2db08b94565c0d582cc53de6cee5fd47-Abstract-Conference.html
|access-date=18 December 2025
}}</ref>
* The [[vertex cover]] problem<ref>{{cite conference
|last1=Antoniadis
|first1=Antonios
|last2=Eliás
|first2=Marek
|last3=Polak
|first3=Adam
|last4=Venzin
|first4=Moritz
|title=Approximation Algorithms for Combinatorial Optimization with Predictions
|book-title=Proceedings of the Thirteenth International Conference on Learning Representations (ICLR 2025)
|publisher=OpenReview
|year=2025
|location=Singapore
|url=https://openreview.net/forum?id=AEFVa6VMu1
|access-date=18 December 2025
}}</ref>

=== Mechanism Design ===

* The [[facility location]] problem<ref>{{cite journal
|last1=Agrawal
|first1=Priyank
|last2=Balkanski
|first2=Eric
|last3=Gkatzelis
|first3=Vasilis
|last4=Ou
|first4=Tingting
|last5=Tan
|first5=Xizhi
|title=Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
|journal=Mathematics of Operations Research
|volume=49
|issue=4
|pages=2626–2651
|year=2024
|publisher=INFORMS
|doi=10.1287/MOOR.2022.0225
|url=https://doi.org/10.1287/moor.2022.0225
|access-date=18 December 2025
}}</ref>

== See also ==
* [[Machine learning]]

== References ==
{{Reflist}}

== External links ==
* [https://algorithms-with-predictions.github.io/ An overview of publications about learning augmented algorithms]

[[Category:Algorithms]]
[[Category:Theoretical computer science]]

Learning augmented algorithm - Revision history

imported>Mountlex: Added more examples of applications with references