In computer science, an online algorithm 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.
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.
No comments:
Post a Comment