CSC3160: Design and Analysis of Algorithms Week 12: Online Algorithms Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Offline algorithms Almost all algorithms we encountered in this course assume that the entire input is given all at once. An exception:Secretary problem. The input is given gradually. We need to respond to each candidate in time. We care about our performance compared to the best one in hindsight 2
Offline algorithms ◼ Almost all algorithms we encountered in this course assume that the entire input is given all at once. ◼ An exception: Secretary problem. ❑ The input is given gradually. ❑ We need to respond to each candidate in time. ❑ We care about our performance compared to the best one in hindsight. 2
Online algorithms The input is revealed in parts. An online algorithm needs to respond to each part (of the input)upon its arrival. The responding actions cannot be canceled/revoked later. We care about the competitive ratio,which compares the performance of an online algorithm to that of the best offline algorithm. Offline:the entire input is given beforehand. 3
Online algorithms ◼ The input is revealed in parts. ◼ An online algorithm needs to respond to each part (of the input) upon its arrival. ◼ The responding actions cannot be canceled/revoked later. ◼ We care about the competitive ratio, which compares the performance of an online algorithm to that of the best offline algorithm. ❑ Offline: the entire input is given beforehand. 3
Ski rental A person goes to a ski resort for a long vacation. Two choices everyday: Rent a ski:$1 per day. ▣Buy a ski::$B once. An unknown factor:the number k of remaining days for ski in this season. When snow melts,the ski resort closes
Ski rental ◼ A person goes to a ski resort for a long vacation. ◼ Two choices everyday: ❑ Rent a ski: $1 per day. ❑ Buy a ski: $𝐵 once. ◼ An unknown factor: the number 𝑘 of remaining days for ski in this season. ❑ When snow melts, the ski resort closes. 4
Offline algorithm If we had known k,then it's easy. If k B,then we should rent everyday.The total cost is k. If k B,then we should buy on day 1.The total cost is B. In any case,the cost is minfk,B}. Question:Without knowing k,how to make decision every day? 5
Offline algorithm ◼ If we had known 𝑘, then it’s easy. ❑ If 𝑘 < 𝐵, then we should rent everyday. The total cost is 𝑘. ❑ If 𝑘 ≥ 𝐵, then we should buy on day 1. The total cost is 𝐵. ◼ In any case, the cost is min{𝑘, 𝐵}. ◼ Question: Without knowing 𝑘, how to make decision every day? 5
Deterministic algorithm There is a simple deterministic algorithm s.t. our cost is at most 2.minfk,B. We then say that the algorithm has a competitive ratio of 2. Algorithm: On each day j<B,rent. On day B,buy. If k B,then our cost is k,which is optimal. ■Ifk≥B,then our cost is B-1+B=2B-1<2B=2·mink,B} 6
Deterministic algorithm ◼ There is a simple deterministic algorithm s.t. our cost is at most 2 ⋅ min{𝑘, 𝐵}. ❑ We then say that the algorithm has a competitive ratio of 2. ◼ Algorithm: On each day 𝑗 < 𝐵, rent. On day 𝐵, buy. ◼ If 𝑘 < 𝐵, then our cost is 𝑘, which is optimal. ◼ If 𝑘 ≥ 𝐵, then our cost is 𝐵 − 1 + 𝐵 = 2𝐵 − 1 < 2𝐵 = 2 ⋅ min 𝑘, 𝐵 6
Randomized algorithm It turns out to exist a randomized algorithm witha competitive ratio of。号≈1.58 The algorithm uses integer programming and linear programming
Randomized algorithm ◼ It turns out to exist a randomized algorithm with a competitive ratio of 𝑒 𝑒−1 ≈ 1.58 ◼ The algorithm uses integer programming and linear programming. 7
Integer programming There is an integer programming to solve the offline version of the ski-rental problem. ■Ve introduce some variables x,zi,z2,.,zk∈ {0,1}. x:indicate whether we eventually buy it. zi:indicate whether we rent on day i. IP: min B·x+=1Z1 s.t.x+z1≥1， j∈[k] x,Z∈{0,1 j∈[k] 8
Integer programming ◼ There is an integer programming to solve the offline version of the ski-rental problem. ◼ We introduce some variables 𝑥, 𝑧1 , 𝑧2 ,… , 𝑧𝑘 ∈ 0,1 . ❑ 𝑥: indicate whether we eventually buy it. ❑ 𝑧𝑖 : indicate whether we rent on day 𝑖. ◼ IP: min 𝐵 ⋅ 𝑥 + σ𝑗=1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1, ∀𝑗 ∈ 𝑘 𝑥, 𝑧𝑗 ∈ 0,1 ∀𝑗 ∈ 𝑘 8
Solution It's not hard to see that the optimal solution to the IP is x=0,zi=1,if k<B x=1,z1=0,ifk≥B 口 same as the previous optimal solution for the offline problem. ■ So the IP does solve the offline problem
Solution ◼ It’s not hard to see that the optimal solution to the IP is ൝ 𝑥 = 0, 𝑧𝑗 = 1, if 𝑘 < 𝐵 𝑥 = 1, 𝑧𝑗 = 0, if 𝑘 ≥ 𝐵 ❑ same as the previous optimal solution for the offline problem. ◼ So the IP does solve the offline problem. 9
Relaxation Relax it to LP. IP: minB·x+=1z S.t.x+zj≥1， j∈[k] x,zj∈{0,1 j∈[k] LP: min B·x+=1Z s.t.x+zj≥1， viEk x≥0，z1≥0， j∈[k] 10
Relaxation ◼ Relax it to LP. ◼ IP: min 𝐵 ⋅ 𝑥 + σ 𝑗 = 1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1 , ∀𝑗 ∈ 𝑘 𝑥 , 𝑧𝑗 ∈ 0 , 1 ∀𝑗 ∈ 𝑘 ◼ L P: min 𝐵 ⋅ 𝑥 + σ 𝑗 = 1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1 , ∀𝑗 ∈ 𝑘 𝑥 ≥ 0 , 𝑧𝑗 ≥ 0 , ∀𝑗 ∈ 𝑘 10