Sammanfattning Detta dokument ger en systematisk studie av flera föreslagna åtgärder för online-algoritmer i samband med ett specifikt problem, nämligen de två serverproblemen på tre linjära punkter. Även om problemet är enkelt, det inkapslar en kärnutmaning i online-algoritmer som är att balansera girighet och anpassningsförmåga. Vi undersöker Competitive Analysis, Max/Max Ratio, Random Order Ratio, Bijective Analysis och Relativa Värsta Order Analys, och avgöra hur dessa åtgärder jämför Greedy Algoritm, Double Coverage, och Lazy Double Coverage, ofta studerade algoritmer i samband med serverproblem. Vi finner att genom Max / Max Ratio och Bijektiv analys, Greedy är den bästa av de tre algoritmerna. Under de andra åtgärderna, Double Coverage och Lazy Double Coverage är bättre, även om Relativa Värsta Order Analys visar att Greedy är ibland bättre. Endast Bijektiv analys och Relativt Värsta Orderanalys indikerar att Lazy Double Coverage är bättre än Double Coverage. Våra resultat ger också det första beviset på optimalitet av en algoritm under Relativa Värsta Order Analys.
Boyar m.fl. Ref gav en systematisk studie av flera åtgärder för en enkel version av k-server-problemet, nämligen de två serverproblemen på tre linjära punkter.
A Comparison of Performance Measures for Online Algorithms
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}