Competitive Analysis Competitive Ratio-quantifies how good an online algorithm is.(Like approximation ratio) -ALG Output of online algorithm -OPT:Output of the optimal offline algorithm CALG Competitive ratio a maxCompetitive Analysis • Competitive Ratio – quantifies how good an online algorithm is. (Like approximation ratio) – 𝐴𝐿𝐺 : Output of online algorithm – 𝑂𝑃𝑇 : Output of the optimal offline algorithm – Competitive ratio 𝛼 = max 𝐴𝐿𝐺 𝑂𝑃𝑇 , 𝑂𝑃𝑇 𝐴𝐿𝐺