📑 Table of Contents▼
Not to be confused with online and offline.

In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand.

In operations research, the area in which online algorithms are developed is called online optimization.

As an example, consider the sorting algorithms selection sort and insertion sort: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm.

Note that the final result of an insertion sort is optimum, i.e., a correctly sorted list. For many problems, online algorithms cannot match the performance of offline algorithms. If the ratio between the performance of an online algorithm and an optimal offline algorithm is bounded, the online algorithm is called competitive.[1]

Not every offline algorithm has an efficient online counterpart.

In grammar theory they are associated with Straight-line grammars.

Definition

edit

Because it does not know the whole input, an online algorithm is forced to make decisions that may later turn out not to be optimal, and the study of online algorithms has focused on the quality of decision-making that is possible in this setting. Competitive analysis formalizes this idea by comparing the relative performance of an online and offline algorithm for the same problem instance. Specifically, the competitive ratio of an algorithm, is defined as the worst-case ratio of its cost divided by the optimal cost, over all possible inputs. The competitive ratio of an online problem is the best competitive ratio achieved by an online algorithm. Intuitively, the competitive ratio of an algorithm gives a measure on the quality of solutions produced by this algorithm, while the competitive ratio of a problem shows the importance of knowing the future for this problem.

Other interpretations

edit

For other points of view on online inputs to algorithms, see

  • streaming algorithm: focusing on the amount of memory needed to accurately represent past inputs;
  • dynamic algorithm: focusing on the time complexity of maintaining solutions to problems with online inputs.

Examples

edit

Some online algorithms:

Online problems

edit

A problem exemplifying the concepts of online algorithms is the Canadian traveller problem. The goal of this problem is to minimize the cost of reaching a target in a weighted graph where some of the edges are unreliable and may have been removed from the graph. However, that an edge has been removed (failed) is only revealed to the traveller when she/he reaches one of the edge's endpoints. The worst case for this problem is simply that all of the unreliable edges fail and the problem reduces to the usual shortest path problem. An alternative analysis of the problem can be made with the help of competitive analysis. For this method of analysis, the offline algorithm knows in advance which edges will fail and the goal is to minimize the ratio between the online and offline algorithms' performance. This problem is PSPACE-complete.

There are many formal problems that offer more than one online algorithm as solution:

See also

edit

References

edit
  1. ^ a b Karp, Richard M. (1992). "On-line algorithms versus off-line algorithms: How much is it worth to know the future?" (PDF). IFIP Congress (1). 12: 416–429. Archived from the original (PDF) on 2007-06-10. Retrieved 17 August 2015.
  2. ^ Dochow, Robert (2016). Online Algorithms for the Portfolio Selection Problem. Springer Gabler.
edit

📚 Artikel Terkait di Wikipedia

Bin packing problem

the offline version of this problem. Offline heuristics, that modify the given list of items e.g. by sorting the items by size. These algorithms are no

Competitive analysis (online algorithm)

to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive

Online and offline

ongoing Online algorithm – Algorithm that begins on possibly incomplete inputs Online and offline algorithms – Algorithm that begins on possibly incomplete

List update problem

hence its strategy may not have the optimum cost as compared to an offline algorithm that gets to see the entire request sequence and devise a complete

Algorithm selection

Algorithm selection (sometimes also called per-instance algorithm selection or offline algorithm selection) is a meta-algorithmic technique to choose

YDS algorithm

and developed by Yao et al. There is both an online and an offline version of the algorithm. Definitions: There is a set of n Jobs J := J 1 , . . . , J

Recommender system

recommendations. Hence any metric that computes the effectiveness of an algorithm in offline data will be imprecise. User studies are rather a small scale. A

Yao's principle

online algorithm has n k + 1 {\displaystyle {\tfrac {n}{k+1}}} expected page faults, over n {\displaystyle n} requests. Instead, an offline algorithm can