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