Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.

Sayan Bhattacharya Monika Henzinger Danupon Nanongkai Xiaowei Wu

Published in: SODA (2021)

Keyphrases

worst case
set cover
greedy algorithm
approximation algorithms
np hard
upper bound
lower bound
greedy heuristics
dynamically updated
average case
running times
computational complexity
error bounds
network flow
decision trees
constraint satisfaction problems
greedy heuristic
linear programming