Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem.

Sepehr Assadi Sanjeev Khanna Yang Li

Published in: SIAM J. Comput. (2021)

Keyphrases

single pass
tight bounds
set cover
stream mining
upper bound
greedy algorithm
approximation algorithms
greedy heuristics
worst case
np hard
network flow
regression forests
data streams
solution space
computational complexity
greedy heuristic
special case
lower bound