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 ⋅ log ⁡ ( m + n ) ) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is 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 ( log 3 ⁡ n ) amortized update time, where n is the number of nodes in the graph.

Authors

• Sayan Bhattacharya
• Monika Henzinger
• Giuseppe Italiano

Keywords

• Dynamic algorithms
• Primal-dual method
• Data structures