Dynamic algorithms via the primal-dual method

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O(f(2))-approximately optimal solution in O(f center dot log(m + n)) amortized update time, where fis the maximum frequency of an element, nis the number of sets, and mis the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O(1)-approximately optimal solution in O(log3n) amortized update time, where nis the number of nodes in the graph. (C) 2018 Elsevier Inc. All rights reserved.