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 𝐴𝐿𝐺 𝑂𝑃𝑇 , 𝑂𝑃𝑇 𝐴𝐿𝐺
Ski rental problem k rounds with unknown k Each rounds you can decide -Rent a ski cost 1 Buy a ski:cost B Optimal cost:min(k,B)
Ski rental problem • 𝑘 rounds with unknown 𝑘 • Each rounds you can decide – Rent a ski : cost 1 – Buy a ski : cost 𝐵 • Optimal cost: min 𝑘, 𝐵
Primal-Dual Method Primal: Dual: k k min B.x+ max yj j=1 j=1 s.t.x+zj≥1， j∈[k] x≥0，z1≥0， j∈[k] s.t. ∑ysB j= y∈[0,1]j x:the 'probability'of buying a ski Zi:the 'probability'of renting a ski at j-th round y:helping make decision
Primal-Dual Method Primal: min 𝐵 ⋅ 𝑥 + 𝑗=1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1, ∀𝑗 ∈ 𝑘 𝑥 ≥ 0, 𝑧𝑗 ≥ 0, ∀𝑗 ∈ 𝑘 Dual: max 𝑗=1 𝑘 𝑦𝑗 𝑠.𝑡. 𝑗=1 𝑘 𝑦𝑗 ≤ 𝐵 ∀𝑗 𝑦𝑗 ∈ [0,1] ∀𝑗 𝑥 : the ‘probability’ of buying a ski 𝑧𝑗 : the ‘probability’ of renting a ski at 𝑗-th round 𝑦𝑗 : helping make decision
Primal-Dual Method Explore a solution (p,d)which is feasible for primal and dual,respectively. -p algorithm's output -d:a lower bound of the optimal solution (recall the weak duality theorem) -Complementary slackness for optimal: ·x(B-∑=1y)=0 ·z（1-y)=0
Primal-Dual Method • Explore a solution (𝑝, 𝑑) which is feasible for primal and dual, respectively. – 𝑝 : algorithm’s output – 𝑑 : a lower bound of the optimal solution (recall the weak duality theorem) – Complementary slackness for optimal: • 𝑥 𝐵 − σ𝑗=1 𝑘 𝑦𝑗 = 0 • 𝑧𝑗 1 − 𝑦𝑗 = 0
Primal-Dual Algorithm ·x=0,yj=0 for each newj=1,2,...,k ifx <1 x←X+ B where c=(1+2)1 1 十 ☑=1-x y5=1 Intuitively,at j-th round,we rent with probability Zi
Primal-Dual Algorithm • 𝑥 = 0, 𝑦𝑗 = 0 for each new 𝑗 = 1,2,… , 𝑘 if 𝑥 < 1 𝑥 ← 𝑥 + 𝑥 𝐵 + 1 𝑐𝐵 , where 𝑐 = 1 + 1 𝐵 𝐵 − 1 𝑧𝑗 = 1 − 𝑥 𝑦𝑗 = 1 • Intuitively, at 𝑗-th round, we rent with probability 𝑧𝑗
Primal-Dual Algorithm ·Pick∈[O,1]uniformly at random. Suppose t is the first day that>=ixj≥， then rent in all days before t and buy on day t. ●Facts: -Rental probability 1- Buying probability:>=1=x
Primal-Dual Algorithm • Pick 𝛼 ∈ [0,1] uniformly at random. • Suppose 𝑡 is the first day that σ𝑗=1 𝑡 𝑥𝑗 ≥ 𝛼, then rent in all days before 𝑡 and buy on day 𝑡. • Facts: – Rental probability : 1 − σ𝑖=1 𝑗−1 𝑥𝑖 = 𝑧𝑗 – Buying probability: σ𝑗=1 𝑡 𝑥𝑗 = 𝑥