Fully Dynamic Weighted Set Cover with Polylogarithmic Worst-Case Recourse

We study fully dynamic weighted set cover under single-element insertions and deletions in a fixed explicit set system. For a universe of size n, maximum element frequency f, polynomially many sets, and fixed O(log n)-bit costs in [1/C, 1] with C = nO(1), we give a deterministic algorithm maintaining an O(log n) approximation with O(fL30) worst-case update time and O(L24) worst-case count recourse, where L = Θ(log(n + m + C + 2)). Recourse counts additions and removals of original set identifiers, and has no multiplicative dependence on f or C. Preprocessing and space are polynomial. The construction schedules gradual replacements by owner mass and bounds their weighted cost using fixed surviving dual witnesses within each density band. A separation rule for replacement appointments yields geometric packing of visible groups; charging their total mass to the largest certificate avoids an extra logarithmic approximation loss. We give explicit resumable greedy resets, coherent private splices, independent retirement queues, and finite-word memory reclamation. The logarithmic exponents and approximation constant are not optimized.