Towards Tight Bounds for the Streaming Set Cover Problem.

Piotr Indyk Sepideh Mahabadi Ali Vakilian

Published in: CoRR (2015)

Keyphrases

tight bounds
set cover
greedy algorithm
upper bound
approximation algorithms
np hard
greedy heuristics
network flow
solution space
greedy heuristic
data streams
worst case
lower bound
convex hull
streaming data
real time
video streaming
np complete
dynamic programming
linear programming