Competitive Analysis of Online Algorithms (Part 2)

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=1JIO4jaAHrA


Duration: 1:03:50
3,585 views
0

Anupam Gupta (Carnegie Mellon University)
https://simons.berkeley.edu/talks/competitive-analysis-online-algorithms-parts-1-and-2-0
Data-Driven Decision Processes Boot Camp

The study of online algorithms forms a vibrant area of research in computer science, considering decision-making under uncertainty. One of the two dominant frameworks is that of competitive analysis. This framework compares the performance of an online algorithm making decisions (without knowledge of the future) to the performance of the best (dynamic) sequence of decisions in hindsight. (This is as opposed to the best static decision.) In these two talks, I will define the model, and survey some representative problems, solution techniques, and proof strategies used in the competitive analysis of online algorithms.



Other Videos By Simons Institute for the Theory of Computing


2022-08-27Understanding, Simplicity, And Decision Trees
2022-08-27The Blackwell-Rao Theorem
2022-08-27Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
2022-08-26Blackwell’s Approachability Theorem
2022-08-26Multi-Distribution Learning, for Robustness, Fairness, and Collaboration
2022-08-26Multicalibration: Towards Fair Decision Making
2022-08-26Mechanism Design with Limited Commitment
2022-08-25(Sequential) Information Design
2022-08-25Machine Learning For Algorithm Design
2022-08-25Competitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
2022-08-25Competitive Analysis of Online Algorithms (Part 2)
2022-08-24Competitive Analysis of Online Algorithms (Part 1)
2022-08-24Online Reinforcement Learning and Regret
2022-08-24Foundations of RL
2022-08-24Foundations of RL
2022-08-23Fundamentals of Markov Decision Processes
2022-08-23Bridging Stochastic and Adversarial Bandits
2022-08-23Adversarial Bandits: Theory and Algorithms
2022-08-23Stochastic Bandits: Foundations and Current Perspectives
2022-08-22Stochastic Bandits: Foundations and Current Perspectives
2022-08-06Deep Learning in Structural Biology and Protein Design: How, Where, and Why


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Data-Driven Decision Processes Boot Camp
Anupam Gupta