Content deleted Content added
Undid revision 1156323630 by Chiragmteam (talk) spam |
No edit summary Tags: Mobile edit Mobile app edit Android app edit |
||
| (2 intermediate revisions by 2 users 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 19 ⟶ 20:
==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}}.
| |||