3 papers
cs.GT2026
Proportionality from Sampled Approvals
Gregory Kehne
How much voter input is necessary in order to ensure representation in multiwinner elections? If voters are randomly selected from an underlying population, how many draws are nece…
cs.DS2024
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.DS2024
Pairwise-Independent Contention Resolution
Anupam Gupta, Jinqiao Hu, Gregory Kehne +1
We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-i…