Algorithmic Analysis: Online vs. Offline Decision-Making
This material discusses online algorithm competitive analysis, the primal-dual method, and various real-world applications like the ski rental problem. It covers concepts such as competitive ratios, primal and dual solutions, and the implementation of the primal-dual algorithm for decision-making. The content elaborates on scenarios where decisions need to be made under uncertainty and limited information, providing insights into optimizing choices in algorithmic settings.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCI 3160 Design and Analysis of Algorithms Tutorial 12 Chengyu Lin
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
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) ??? : Output of online algorithm ??? : Output of the optimal offline algorithm ??? ???,??? Competitive ratio ? = max ???
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: ? ? min ? ? + ?? max ?? ?=1 ?=1 ? ?.?. ? + ?? 1, ? 0,?? 0, ? ? ? ? ?.?. ?? ? ? ?=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 (?,?) 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 ? = 0,??= 0 for each new ? = 1,2, ,? if? < 1 ? ? +? ??= 1 ? ??= 1 Intuitively, at ?-th round, we rent with probability ?? ? ??, where ? = 1 +1 1 ?+ 1 ?
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: ? 1??= ?? ??= ? Rental probability : 1 ?=1 Buying probability: ?=1 ?
Competitive ratio ???? ??? ???? ??? ?????? ??? = ??? ?????? ??? (1 +1 ?)???? ??? Combine together, competitive ratio ? ? 1
End Questions?
