香港中文大学：《Design and Analysis of Algorithms》课程教学资源（辅导课件）tutorial 12

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 𝑡 𝑥𝑗 = 𝑥