Algorithms, Combinatorics & Optimization (ACO)
Gregory Kehne (Harvard)
February 24, 2023
Skiles 005 - 1:00 pm
Title: Online Covering: Prophets, Secretaries, and Samples
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 \Omega(\log n) and circumventing the \Omega(\log m \log n) lower bound known in adversarial order. We then leverage this O(\log mn)-competitive algorithm to solve this problem in the prophet setting, where constraints are sampled from a sequence of known distributions. Our reduction in fact relies only on samples from these distributions, in a manner evocative of prior work on single-sample prophet inequalities for online packing problems. We present sample guarantees in the prophet setting, as well as in the setting where random samples from an adversarial instance are revealed at the outset.
This talk is based on joint work with Anupam Gupta and Roie Levin, part of which appeared at FOCS 2021.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
