research
∙
04/04/2023
Set Covering with Our Eyes Wide Shut
In the stochastic set cover problem (Grandoni et al., FOCS '08), we are ...
share
research
∙
04/04/2023
Chasing Positive Bodies
We study the problem of chasing positive bodies in ℓ_1: given a sequence...
research
∙
11/12/2021
Random Order Set Cover is as Easy as Offline
We give a polynomial-time algorithm for OnlineSetCover with a competitiv...
research
∙
09/02/2020
Fully-Dynamic Submodular Cover with Bounded Recourse
In submodular covering problems, we are given a monotone, nonnegative su...
research
∙
08/23/2020
Streaming Submodular Matching Meets the Primal-Dual Method
We study streaming submodular maximization subject to matching/b-matchin...
research
∙
11/18/2019