Roie Levin

activity

20152026

collaborators

Showing 2023Show all

2 papers · 1 filter

cs.DS2023

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 $S$ of $m$ sets over a universe $U$ of size $N$ , and a distribution $…

cs.DS2023

Chasing Positive Bodies

Sayan Bhattacharya, Niv Buchbinder, Roie Levin +1

We study the problem of chasing positive bodies in $ℓ_{1}$ : given a sequence of bodies $K_{t} = {x^{t} \in R_{+}^{n} ∣ C^{t} x^{t} \geq 1, P^{t} x^{t} \leq 1}$ revealed online…