- Series
- ACO Student Seminar
- Time
- Friday, February 24, 2023 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Gregory Kehne – Harvard Computer Science – gkehne@g.harvard.edu – https://gregorykehne.com/
- Organizer
- Abhishek Dhawan
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.