Evaluation for Online Algorithms Competitive Ratio(CR) CR Cost of an online algorithm Cost of the corresponding offline algorithm Deterministic algorithms MaxSum(m) o CR= minG(T, W, P U)and VvEv MaxSum(OPT) The worst trichromatic graph The worst arrival order Randomized algorithms E[MaxSum(m) o Cr= ming(T, w, P, U)and VvEv MaxSum(OPT The expected performance is com pared⚫ Competitive Ratio (CR) ⚫ 𝐶𝑅 = 𝐂𝐨𝐬𝐭 𝐨𝐟 𝐚𝐧 𝐨𝐧𝐥𝐢𝐧𝐞 𝐚𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 𝐂𝐨𝐬𝐭 𝐨𝐟 𝐭𝐡𝐞 𝐜𝐨𝐫𝐫𝐞𝐬𝐩𝐨𝐧𝐝𝐢𝐧𝐠 𝐨𝐟𝐟𝐥𝐢𝐧𝐞 𝐚𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 ⚫ Deterministic algorithms o CR = 𝑚𝑖𝑛∀𝐺 𝑇,𝑊,𝑃,𝑈 𝑎𝑛𝑑 ∀𝑣∈𝑉 𝑀𝑎𝑥𝑆𝑢𝑚(𝑀) 𝑀𝑎𝑥𝑆𝑢𝑚(𝑂𝑃𝑇) ⚫ Randomized algorithms o CR = 𝑚𝑖𝑛∀𝐺 𝑇,𝑊,𝑃,𝑈 𝑎𝑛𝑑 ∀𝑣∈𝑉 𝔼[𝑀𝑎𝑥𝑆𝑢𝑚 𝑀 ] 𝑀𝑎𝑥𝑆𝑢𝑚(𝑂𝑃𝑇) Evaluation for Online Algorithms The worst arrival order The worst trichromatic graph The expected performance is compared. 30