Fully Dynamic Set Cover: Worst-Case Recourse and Update Time

We give the first algorithms for fully dynamic set cover with non-trivial worst-case guarantees for both recourse and update time. Specifically, we achieve O(logn) recourse and f· log(n) update time in the worst-case, for both approximation regimes: O(logn) and O(f) approximation. Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained f· log(n) update time in the worst-case but at the cost of ω(m) worst-case recourse. (Here, m, n, f respectively denote the number of sets, maximum number of elements, and maximum frequency.)

Duke Scholars

Author Debmalya Panigrahi Computer Science