Sariel Har-Peled

activity

20112026

most citedTowards Tight Bounds for the Streaming Set Cover Problem

33 citations · 45 across the 30 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

Quickly Avoiding a Random Catastrophe

Stav Ashur, Sariel Har-Peled

We study the problem of constructing simulations of a given randomized search algorithm \texttt{alg} with expected running time $O (O lo g O)$ , where $\mathcal{…

cs.DS2021★ 1 cited

On Competitive Permutations for Set Cover by Intervals

Sariel Har-Peled, Jiaqi Cheng

We revisit the problem of computing an optimal partial cover of points by intervals. We show that the greedy algorithm computes a permutation $Π = π_{1}, π_{2}, \dots$ of the intervals…

cs.DS2015★ 33 cited

Towards Tight Bounds for the Streaming Set Cover Problem

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi +1

We consider the classic Set Cover problem in the data stream model. For $n$ elements and $m$ sets ( $m \geq n$ ) we give a $O (1/ δ)$ -pass algorithm with a strongly sub-linear $\tilde{O…