Online Covering: Secretaries, Prophets and Universal Maps
From Google TechTalks · 57:22
Show by Google TechTalks
A Google TechTalk, presented by Roie Levin, 2022-02-23ABSTRACT: We give a polynomial-time algorithm for online covering IPs with a competitive ratio of O(log mn) when the constraints are revealed in random order, essentially matching the best possible offline bound of O(log n) and circumventing the Ω(log m log n) lower bound known in adversarial order. We then use this result to give an O(log mn) competitive algorithm for the prophet version of this problem, where constraints are sampled from a sequence of known distributions (in fact, our algorithm works even when only a single sample from each of the distributions is given). Since our algorithm is universal, as a byproduct we establish that only O(n) samples are necessary to build a universal map for online covering IPs with competitive ratio O(log mn) on input sequences of length n.Uploaded 03-03-23This talk is based on joint work with Anupam Gupta and Gregory Kehne, the first half of which appeared at FOCS 2021.Bio: Roie is Fulbright Postdoctoral Fellow at Tel Aviv University, working with Niv Buchbinder. He received his PhD in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University where he was advised by Anupam Gupta. Before that, he worked as a research engineer at the Allen Institute for Artificial Intelligence, and before that he received bachelor degrees in math and computer science from Brown University. Roie's main research interests are algorithms for uncertain environments (online/dynamic/streaming algorithms), and submodular optimization.A Google Research Algorithm Seminar.
More episodes of Google TechTalks
More episodes
- Making Great Decisions
- Streaming Private Continual Counting via Binning
- Distributed Testing with SmartFrog
- Differentially Private Synthetic Data without Training
- A Dynamic Network Layer for Advanced Cloud Computing
- Data Representation/Laplace Operator
- Persistent Pre-Training Poisoning of LLMs
- Threat Models for Memorization: Privacy, Copyright, and Everything In-Between
- Technology Assisted Reading Acquisition: Children Acquiring Literacy Naturally
- sex on the internet, the realities of porn, sexual privacy,
PodSearch is a free, independent podcast search engine. Read about PodSearch, the privacy policy or contact us.