Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
No edit summary Tags: Mobile edit Mobile app edit Android app edit |
||
| (One intermediate revision by one other user not shown) | |||
Line 1:
{{Short description|Method for analyzing online algorithms}}
'''Competitive analysis''' is a method invented for analyzing [[online algorithm]]s, 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.
Line 20 ⟶ 21:
==References==
*{{citation|title=Amortized efficiency of list update and paging rules|first1=D.|last1=Sleator|author1-link=Daniel Sleator|first2=R.|last2=Tarjan|author2-link=Robert Tarjan|journal=Communications of the ACM|year=1985|doi=10.1145/2786.2793|volume=28|issue=2|pages=202–208|doi-access=free}}.
*{{citation|contribution=Competitive analysis of distributed algorithms|first=James|last=Aspnes|year=1998|doi=10.1007/BFb0029567|title=Online Algorithms: The State of the Art|series=Lecture Notes in Computer Science|volume=1442|pages=118–146|isbn=978-3-540-64917-5 |editor1-first=A.|editor1-last=Fiat|editor1-link=Amos Fiat|editor2-first=G. J.|editor2-last=Woeginger|editor2-link= Gerhard J. Woeginger}}.
*{{citation|last1=Borodin|first1=A.|author1-link=Allan Borodin|last2=El-Yaniv|first2=R.|year=1998|title=Online Computation and Competitive Analysis|publisher=Cambridge University Press|isbn=0-521-56392-5}}.
*{{citation|last1=Awerbuch|first1=B.|last2=Kutten|first2=S.|last3=Peleg|first3=D.|authorlink2=Shay Kutten|year=1992|contribution=Competitive Distributed Job Scheduling|title=ACM STOC, Victoria, BC, Canada}}.
| |||