Online Covering: Secretaries, Prophets and Universal Maps
Host
Noah Golowich
MIT
Note the special start time (4:15pm).
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.
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.