Competitive Analysis of Online Algorithms (Part 1)

on YouTube ↗56m

" summary

Survey defines competitive ratio, uses rent-or-buy to show deterministic best policy buys at B days giving ratio ~2 and randomized optimal ratio is e/(e-1) ≈1.58 via LP/Yao minimax. Methods: model online algorithms as distributions over deterministic strategies, analyze worst-case instances and dual LPs. Second problem gives marking strategy on uniform metric: deterministic is N‑competitive, randomizing to pick unmarked locations yields O(log n) by coupon‑collector style analysis.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 11:46Worst Case Input
3. 17:11Oblivious Algorithms
4. 28:22Minimax Principle

" related talks

• 01h 00mContinuous Methods 4Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka, Reza Eghbali · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 08mData Driven Optimization Models and AlgorithmsYinyu Ye · Optimization, Statistics and Uncertainty
• 41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and OptimizationNegin Golrezaei · Mathematics of Online Decision Making 2020
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 41mCompetitive Algorithms for Online ControlYisong Yue · Mathematics of Online Decision Making 2020
• 40mA Bayesian Approach to Online Resource AllocationSid Banerjee · Real-Time Decision Making 2018
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 40mOnline Ad Allocation: Robust Optimization for Repeated AuctionsVahab Mirrokni · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)