(1 + ε)-Approximate Incremental Matchings in Linear Time

We study the dynamic matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-optimal matching of the graph with small update time. We present a deterministic algorithm for bipartite matching and a randomized algorithm for matching in general graphs. For constant ε>0, both algorithms obtain a (1+ε) approximation and run in amortized constant time per edge insertion.

Joint work with Fabrizio Grandoni, Anupam Gupta, Piotr Sankowski and Chris Schwiegelshohn.