A learning augmented algorithm is an algorithm that can make use of a prediction to improve its performance. [1] 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.
A learning augmented algorithm typically takes an input . Here is a problem instance and is the advice: a prediction about a certain property of the optimal solution. The type of the problem instance and the prediction depend on the algorithm. Learning augmented algorithms usually satisfy the following two properties:
Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose machine learning can be used.[ citation needed]
The binary search algorithm is an algorithm for finding elements of a sorted list . It needs steps to find an element with some known value in a list of length . With a prediction for the position of , the following learning augmented algorithm can be used. [1]
The error is defined to be , where is the real index of . In the learning augmented algorithm, probing the positions takes steps. Then a binary search is performed on a list of size at most , which takes steps. This makes the total running time of the algorithm . 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 . Then the algorithm takes at most steps, so the algorithm is robust.
Learning augmented algorithms are known for:
A learning augmented algorithm is an algorithm that can make use of a prediction to improve its performance. [1] 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.
A learning augmented algorithm typically takes an input . Here is a problem instance and is the advice: a prediction about a certain property of the optimal solution. The type of the problem instance and the prediction depend on the algorithm. Learning augmented algorithms usually satisfy the following two properties:
Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose machine learning can be used.[ citation needed]
The binary search algorithm is an algorithm for finding elements of a sorted list . It needs steps to find an element with some known value in a list of length . With a prediction for the position of , the following learning augmented algorithm can be used. [1]
The error is defined to be , where is the real index of . In the learning augmented algorithm, probing the positions takes steps. Then a binary search is performed on a list of size at most , which takes steps. This makes the total running time of the algorithm . 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 . Then the algorithm takes at most steps, so the algorithm is robust.
Learning augmented algorithms are known for: