@inproceedings{2f0a7e9cc3e742b49a7ac056fd063bdc,

title = "Random Order Online Set Cover is as Easy as Offline",

abstract = "We give a polynomial-time algorithm for Online-SetCover with a competitive ratio of O(log mn) when the elements are revealed in random order, matching the best possible offline bound of O(log n) when the number of sets m is polynomial in the number of elements n, and circumventing the Ω(log m log n) lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order. The algorithm is a multiplicative-weights-based round-and-solve approach we call LearnOrCover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for Setcover that performs a single pass through the elements, which may be of independent interest.",

keywords = "Beyond Worst Case, Online Algorithms, Random Order, Set Cover",

author = "Anupam Gupta and Gregory Kehne and Roie Levin",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 ; Conference date: 07-02-2022 Through 10-02-2022",

year = "2022",

doi = "10.1109/FOCS52979.2021.00122",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "1253--1264",

booktitle = "Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021",

}