Online Covering: Secretaries, Prophets and Universal Maps

A Google TechTalk, presented by Roie Levin, 2022-02-23 ABSTRACT: 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. This 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.