STOC 2020 - Online Algorithms

Explore cutting-edge research in online algorithms through this 38-minute conference talk from STOC 2020, presented by the Association for Computing Machinery (ACM). Delve into advanced topics such as caching with time windows, online vector balancing, and primal-dual matching. Learn about the latest developments in standard caching, offline vector balancing, and the k-server problem. Gain insights into constant competitive ratios and their proofs. The talk concludes with audience questions and a preview of the next presentation, offering a comprehensive overview of current trends and challenges in the field of online algorithms.

Introduction
Caching with time windows
Whats known
Other results
Standard Caching
Conclusions
Online Vector Balancing
Offline Vector Balancing
Correlation
Conclusion
Online Primal Dual Matching
Results
Solution
Audience Questions
Next talk
Case
HK Server Problem
Constant Competitive Ratio
Our Contribution
Proof