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. 3Online 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