1 citations · 2 across the 11 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.DS2021
Random Order Set Cover is as Easy as Offline
Anupam Gupta, Gregory Kehne, Roie Levin
We give a polynomial-time algorithm for OnlineSetCover with a competitive ratio of when the elements are revealed in random order, essentially matching the best possib…
cs.GT2021
Can Buyers Reveal for a Better Deal?
Daniel Halpern, Gregory Kehne, Jamie Tucker-Foltz
We study market interactions in which buyers are allowed to credibly reveal partial information about their types to the seller. Previous recent work has studied the special case o…