14 Evaluation for Online Algorithms Competitive Ratio(CR) ●CR= Cost of an online algorithm Cost of the corresponding offline algorithm Input Models Adversarial Model worst-Case Analysis) Minsum(m) o CRa maxVG(T, W, U)andvvev min Sum(OPT The worst bipartite graph The worst arrival order Random Order Model(Average-Case Analysis) E MinSum(m) CRpo maxvG(T, W,]) MinSum(OPT) The expectation of the total cost of all possible The worst bipartite graph arrival ordersThe worst arrival order Evaluation for Online Algorithms ⚫ Competitive Ratio (CR) ⚫ 𝐶𝑅 = 𝑪𝒐𝒔𝒕 𝒐𝒇 𝒂𝒏 𝒐𝒏𝒍𝒊𝒏𝒆 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 𝑪𝒐𝒔𝒕 𝒐𝒇 𝒕𝒉𝒆 𝒄𝒐𝒓𝒓𝒆𝒔𝒑𝒐𝒏𝒅𝒊𝒏𝒈 𝒐𝒇𝒇𝒍𝒊𝒏𝒆 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 ⚫ Input Models ⚫ Adversarial Model (Worst-Case Analysis) o 𝐶𝑅𝐴 = 𝐦𝐚𝐱∀𝐺 𝑇,𝑊,𝑈 𝑎𝑛𝑑∀𝑣∈𝑉 𝑀𝑖𝑛𝑆𝑢𝑚(𝑀) 𝑀𝑖𝑛𝑆𝑢𝑚(𝑂𝑃𝑇) ⚫ Random Order Model (Average-Case Analysis) o 𝐶𝑅𝑅𝑂 = 𝐦𝐚𝐱∀𝐺 𝑇,𝑊,𝑈 𝔼[𝑀𝑖𝑛𝑆𝑢𝑚 𝑀 ] 𝑀𝑖𝑛𝑆𝑢𝑚(𝑂𝑃𝑇) The worst bipartite graph The worst bipartite graph The expectation of the total cost of all possible arrival orders 14