Skip to main content

Design of Dynamic Algorithms via Primal-Dual Method

Sayan Bhattacharya ( University of Warwick )

The primal-dual method is a general technique that is widely used to design efficient (static) algorithms for optimization problems. We present the first application of this technique in a dynamic setting.

We consider the problem of maintaining an approximately maximum matching in a dynamic graph. Specifically, we have an input graph G = (V, E) with n nodes. The node-set of the graph remains unchanged over time, but the edge-set is dynamic. At each time-step an adversary either inserts an edge into the graph, or deletes an already existing edge from the graph. The goal is to maintain a matching of approximately maximum size in G with small update time.

We present a clean primal-dual algorithm for this problem that maintains a (2+\epsilon)-approximate maximum fractional matching in O(\log n/\epsilon^2) amortized update time. We also describe several extensions to this basic framework, which allow us to obtain a new efficient dynamic algorithm for maintaining a (2+\epsilon)-approximate maximum ''integral'' matching, and to maintain a (2+\epsilon)-approximate maximum fractional matching in O(poly log n) ''worst case'' update time.

Based on joint work with Monika Henzinger, Giuseppe Italiano and Danupon Nanongkai.

 

 

Share this: