4 papers · 1 filter
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…
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 $…
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…
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.