Competitive analysis (online algorithm): Difference between revisions

Revision as of 04:58, 1 February 2011

Revision as of 06:23, 4 April 2011

Line 1:

'''Competitive analysis''' is a method invented for analyzing [[Online algorithm|online algorithms]], in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal ''offline algorithm'' that can view the sequence of requests in advance. An algorithm is ''competitive'' if its ''competitive ratio''—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional [[Best, worst and average case|worst-case analysis]], where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm.

For many algorithms, performance is dependent on not only on the size of the inputs, but also on their values. One such example is the [[quicksort]] algorithm, which sorts an array of elements. Such data-dependent algorithms are analysed for average-case and worst-case data. Competitive analysis is a way of doing worst case analysis for on-line and [[randomized algorithm]]s, which are typically data dependent.

In competitive analysis, one imagines an "adversary" that deliberately chooses difficult data, to maximize the ratio of the cost of the algorithm being studied and some optimal algorithm. Adversaries range in power from the ''oblivious adversary'', which has no knowledge of the random choices made by the algorithm pitted against it, to the ''adaptive adversary'' that has full knowledge of how an algorithm works and its internal state at any point during its execution. Note that this distinction is only meaningful for randomized algorithms. For a deterministic algorithm, either adversary can simply compute what state that algorithm must have at any time in the future, and choose difficult data accordingly.