Tight bounds for single-pass streaming complexity of the set cover problem.

Sepehr Assadi Sanjeev Khanna Yang Li

Published in: STOC (2016)

Keyphrases

single pass
tight bounds
set cover
stream mining
upper bound
greedy algorithm
worst case
approximation algorithms
np hard
network flow
regression forests
greedy heuristic
lower bound
streaming data
greedy heuristics
data streams
data mining
convex hull
metaheuristic
association rules
neural network