Competitive analysis (online algorithm)

Competitive analysis (online algorithm)

Competitive analysis is a method invented for analyzing 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 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 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 algorithms, 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.

For example, the quicksort algorithm chooses one element, called the "pivot", that is, on average, not too far from the center value of the data being sorted. Quicksort then separates the data into two piles, one of which contains all elements with value less than the value of the pivot, and the other containing the rest of the elements. If quicksort chooses the pivot in some deterministic fashion (for instance, always choosing the first element in the list), then it is easy for an adversary to arrange the data beforehand so that quicksort will perform in worst-case time. If, however, quicksort chooses some random element to be the pivot, then an adversary without knowledge of what random numbers are coming up cannot arrange the data to guarantee worst-case execution time for quicksort.

The classic on-line problem first analysed with competitive analysis (Sleator & Tarjan 1985) is the List update problem: Given a list of items and a sequence of requests for the various items, minimize the cost of accessing the list where the elements closer to the front of the list cost less to access. (Typically, the cost of accessing an item is equal to its position in the list.) After an access, the list may be rearranged. Most rearrangements have a cost. The Move-To-Front algorithm simply moves the requested item to the front after the access, at no cost. The Transpose algorithm swaps the accessed item with the item immediately before it, also at no cost. Classical methods of analysis showed that Transpose is optimal in certain contexts. In practice, Move-To-Front performed much better. Competitive analysis was used to show that an adversary can make Transpose perform arbitrarily badly compared to an optimal algorithm, whereas Move-To-Front can never be made to incur more than twice the cost of an optimal algorithm.

In the case of online requests from a server, competitive algorithms are used to overcome uncertainties about the future. That is, the algorithm does not "know" the future, while the imaginary adversary (the "competitor") "knows". Similarly, competitive algorithms were developed for distributed systems, where the algorithm has to react to a request arriving at one location, without "knowing" what has just happened in a remote location. This setting was presented in (Awerbuch, Kutten & Peleg 1992).

See also

References

  • Sleator, D.; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM 28 (2): 202–208, doi:10.1145/2786.2793 .
  • Aspnes, James (1998), "Competitive analysis of distributed algorithms", in Fiat, A.; Woeginger, G. J., Online Algorithms: The State of the Art, Lecture Notes in Computer Science, 1442, pp. 118–146, doi:10.1007/BFb0029567 .
  • Borodin, A.; El-Yaniv, R. (1998), Online Computation and Competitive Analysis, Cambridge University Press, ISBN 0-521-56392-5 .
  • Awerbuch, B.; Kutten, S.; Peleg, d. (1992), "Competitive Distributed Job Scheduling", ACM STOC, Victoria, BC, Canada .

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Competitive analysis — may refer to: Competitor analysis Competitive analysis (online algorithm) This disambiguation page lists articles associated with the same title. If an internal link led you here, you may …   Wikipedia

  • Adversary (online algorithm) — In computer science, an online algorithm measures its competitiveness against different adversary models. For deterministic algorithms, the adversary is the same, the adaptive offline adversary. For randomized online algorithms competitiveness… …   Wikipedia

  • Online algorithm — 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… …   Wikipedia

  • Online algorithm — En informatique, un algorithme online (algorithme en ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les… …   Wikipédia en Français

  • Analysis — (from Greek ἀνάλυσις , a breaking up ) is the process of breaking a complex topic or substance into smaller parts to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle,… …   Wikipedia

  • Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list …   Wikipedia

  • List of algorithm general topics — This is a list of algorithm general topics, by Wikipedia page. * Analysis of algorithms * Ant colony algorithm * Approximation algorithm * Best and worst cases * Big O notation * Combinatorial search * Competitive analysis * Computability theory… …   Wikipedia

  • Amortized analysis — In computer science, especially analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst case sequence of operations. Amortized analysis differs from average case performance in that… …   Wikipedia

  • Ski rental problem — The ski rental problem is the name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one time cost which eliminates or reduces the repeating cost. The problem Many online problems have… …   Wikipedia

  • Job shop scheduling — For other uses, see Scheduling. Job shop scheduling (or Job shop problem) is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”