3 papers
cs.DS2020
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…
cs.LG2020
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…
cs.DS2018
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.