Online algorithm

An online algorithm is a special type of algorithm that does not know the input from the beginning in its entirety, but receives it in batches. After each turn, the algorithm must provide a partial response.

Problems solved by online algorithms are called online problems. Routine or scheduling is a natural example - as it is generally unknown which processes will require resources in the future, it is only necessary to allocate them based on the current situation. A more mathematical example is online coloring - starting with an empty graph, each vertex adds a single vertex with all edges. The task of the algorithm is to choose a color for it so that coloration is acceptable and the colors are as low as possible.

Online algorithms are also called classic algorithms, which do not need to read entire input data, but can process them on a regular basis. Such algorithms are, for example, the KMP pattern matching algorithm, or the ukkonen algorithm for the construction of a suffix tree. competitiveness

Of course, knowing full data from the beginning, you probably would have found a better solution to your problem (more efficient memory allocation, fewer colors used). Therefore, it is advisable to compare the solution given by the online algorithm with the optimal solution on the same input. If for every possible data the online algorithm yields at most c {\displaystyle c} times worse than optimal, we say that the algorithm is c {\displaystyle c} -competitive. number c {\displaystyle c} is called the competitiveness factor of the algorithm. Generalization of this concept is a function of competitiveness: it is such a function f {\displaystyle f} that for any input data the online algorithm gives the result no worse than f ( w ) {\displaystyle f(w)} where w {\displaystyle w} is the optimal result.

wiki