BIU theory seminar - April 19 : Roie Levin - Set Covering with our Eyes Wide Shut
1 view
Skip to first unread message
Arnold Filtser
Apr 13, 2023, 2:37:32 AM4/13/23
to BIU Theory Seminar, eio...@gmail.com
Hello all,
Next week (Wed April 19) we will meet for our theory seminar.
Location: Building 605 room 14
See you there,
Arnold
Speaker: Roie Levin (TAU)
Title: Set Covering with our Eyes Wide Shut
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.
Title: Set Covering with our Eyes Wide Shut
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.
Reply all
Reply to author
Forward
0 new messages