1 citations · 2 across the 11 of their papers we have counts for
14 papers
Dynamic Contention Resolution Schemes
Moran Feldman, Gregory Kehne, Roie Levin +1
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs…
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…
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…
The Distortion of Binomial Voting Defies Expectation
Yannai A. Gonczarowski, Gregory Kehne, Ariel D. Procaccia +2
In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outc…
Set Covering with Our Eyes Wide Shut
Anupam Gupta, Gregory Kehne, Roie Levin
In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection of sets over a universe of size , and a distribution $…
Representation with Incomplete Votes
Daniel Halpern, Gregory Kehne, Ariel D. Procaccia +2
Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful, based on whether participants agree or disagree with…
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…
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…
An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
D Ellis Hershkowitz, Gregory Kehne, R. Ravi
In the weighted minimum strongly connected spanning subgraph (WMSCSS) problem we must purchase a minimum-cost strongly connected spanning subgraph of a digraph. We show that half-i…
The Phantom Steering Effect in Q&A Websites
Nicholas Hoernle, Gregory Kehne, Ariel D. Procaccia +1
Badges are commonly used in online platforms as incentives for promoting contributions. It is widely accepted that badges "steer" people's behavior toward increasing their rate of…
Reverse Greedy is Bad for k-Center
D Ellis Hershkowitz, Gregory Kehne
We show the reverse greedy algorithm is between a - and a -approximation for -center.
Bipyramid Decompositions of Multi-crossing Link Complements
Colin Adams, Gregory Kehne
Generalizing previous constructions, we present a dual pair of decompositions of the complement of a link L into bipyramids, given any multi-crossing projection of L. When L is hyp…
Generalized bipyramids and hyperbolic volumes of tiling links
Colin Adams, Aaron Calderon, Xinyi Jiang +4
We present explicit geometric decompositions of the complement of tiling links, which are alternating links whose projection graphs are uniform tilings of the 2-sphere, the Euclide…
Volume and Determinant Densities of Hyperbolic Rational Links
Colin Adams, Aaron Calderon, Xinyi Jiang +4
The volume density of a hyperbolic link is defined as the ratio of hyperbolic volume to crossing number. We study its properties and a closely-related invariant called the determin…