CSCI 3160 Design and Analysis of Algorithms Tutorial 12 Chengyu Lin
CSCI 3160 Design and Analysis of Algorithms Tutorial 12 Chengyu Lin
Outline 。Online Algorithm Competitive Analysis ·Primal-Dual Method
Outline • Online Algorithm • Competitive Analysis • Primal-Dual Method
Online vs.Offline Each round part of the input is revealed Make irrevocable decision each round Example:Secretary Problem
Online vs. Offline • Each round part of the input is revealed • Make irrevocable decision each round • Example: Secretary Problem
Applications Real-world problems(secretary problem) Streaming Algorithm(memory limited computation,big data) Online Machine Learning
Applications • Real-world problems (secretary problem) • Streaming Algorithm (memory limited computation, big data) • Online Machine Learning
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 max
Competitive 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 𝐴𝐿𝐺 𝑂𝑃𝑇 , 𝑂𝑃𝑇 𝐴𝐿𝐺