Konkurrensanalys (onlinealgoritm)

Konkurrensanalys är en metod som uppfunnits för att analysera onlinealgoritmer , där prestandan hos en onlinealgoritm (som måste tillfredsställa en oförutsägbar sekvens av förfrågningar, slutföra varje förfrågan utan att kunna se framtiden) jämförs med prestandan hos en optimal offlinealgoritm som kan se sekvensen av förfrågningar i förväg. En algoritm är konkurrenskraftig om dess konkurrensförhållande – förhållandet mellan dess prestanda och offlinealgoritmens prestanda – är begränsat. Till skillnad från traditionell worst-case-analys , där prestandan för en algoritm endast mäts för "hårda" indata, kräver konkurrensanalys att en algoritm presterar bra både på hårda och enkla indata, där "hård" och "lätt" definieras av prestandan av den optimala offlinealgoritmen.

För många algoritmer beror prestandan inte bara på storleken på ingångarna utan också på deras värden. Till exempel, sortering av en uppsättning element varierar i svårighetsgrad beroende på den ursprungliga ordningen. Sådana databeroende algoritmer analyseras för genomsnitts- och värstafallsdata. Konkurrensanalys är ett sätt att göra worst case-analys för online- och randomiserade algoritmer, som vanligtvis är databeroende.

I konkurrensanalys föreställer man sig en "motståndare" som medvetet väljer svåra data, för att maximera förhållandet mellan kostnaden för den algoritm som studeras och någon optimal algoritm. När man överväger en randomiserad algoritm måste man ytterligare skilja mellan en omedveten motståndare , som inte har någon kunskap om de slumpmässiga val som gjorts av algoritmen som ställs mot den, och en adaptiv motståndare som har full kunskap om algoritmens interna tillstånd när som helst under dess utförande. . (För en deterministisk algoritm finns det ingen skillnad; båda motståndarna kan helt enkelt beräkna vilket tillstånd den algoritmen måste ha när som helst i framtiden och välja svåra data därefter.)

Till exempel väljer quicksort -algoritmen ett element, kallat "pivot", det vill säga i genomsnitt inte alltför långt från mittvärdet för den data som sorteras. Quicksort separerar sedan data i två högar, varav den ena innehåller alla element med ett värde som är mindre än värdet på pivoten, och den andra innehåller resten av elementen. Om quicksort väljer pivoten på något deterministiskt sätt (till exempel genom att alltid välja det första elementet i listan), är det lätt för en motståndare att ordna data i förväg så att quicksort kommer att fungera i värsta fall. Om däremot quicksort väljer något slumpmässigt element som pivot, kan en motståndare utan kunskap om vilka slumptal som kommer upp inte ordna data för att garantera värsta tänkbara exekveringstid för quicksort.

Det klassiska onlineproblemet som först analyserades med konkurrensanalys ( Sleator & Tarjan 1985 ) är listuppdateringsproblemet : Med tanke på en lista med artiklar och en sekvens av förfrågningar för de olika objekten, minimera kostnaden för att komma åt listan där elementen närmare framsidan av listan kostar mindre att komma åt. (Vanligtvis är kostnaden för att komma åt ett objekt lika med dess position i listan.) Efter en åtkomst kan listan ordnas om. De flesta omarrangemang har en kostnad. Move -To-Front-algoritmen flyttar helt enkelt det begärda föremålet till fronten efter åtkomsten, utan kostnad. Transponeringsalgoritmen byter det åtkomliga objektet med objektet omedelbart före det, även det utan kostnad . Klassiska analysmetoder visade att Transpose är optimalt i vissa sammanhang. I praktiken presterade Move-To-Front mycket bättre. Konkurrensanalys användes för att visa att en motståndare kan få Transpose att prestera godtyckligt dåligt jämfört med en optimal algoritm, medan Move-To-Front aldrig kan få mer än dubbelt så mycket kostnad som en optimal algoritm.

I fallet med onlineförfrågningar från en server används konkurrenskraftiga algoritmer för att övervinna osäkerheter om framtiden. Det vill säga att algoritmen inte "vet" framtiden, medan den imaginära motståndaren ("konkurrenten") "vet". På liknande sätt utvecklades konkurrenskraftiga algoritmer för distribuerade system, där algoritmen måste reagera på en förfrågan som kommer till en plats, utan att "veta" vad som just har hänt på en avlägsen plats. Denna inställning presenterades i ( Awerbuch, Kutten & Peleg 1992 ) .

Se även

Sleator, D. ; Tarjan, R. (1985), "Amortized efficiency of list update and pageing rules", Communications of the ACM , 28 (2): 202–208, doi : 10.1145/2786.2793 .
Aspnes, James (1998), "Competitive analysis of distributed algorithms", i Fiat, A. ; Woeginger, GJ (red.), Online Algorithms: The State of the Art , Lecture Notes in Computer Science, vol. 1442, s. 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, Kanada .