New Iterative Algorithms for Weighted Matching

Abstract

Matching is an important combinatorial problem with a number of
practical applications. Even though there exist polynomial time solutions
to most matching problems, there are settings where these are too slow.
This has led to the development of several fast approximation algorithms
that in practice compute matchings very close to the optimal.
The current paper introduces a new deterministic approximation
algorithm named G 3 , for weighted matching. The algorithm is based on
two main ideas, the first is to compute heavy subgraphs of the original
graph on which we can compute optimal matchings. The second idea is
to repeatedly merge these matchings into new matchings of even higher
weight than the original ones. Both of these steps are achieved using
dynamic programming in linear or close to linear time.
We compare G 3 with the randomized algorithm GPA+ROMA which
is the best known algorithm for this problem. Experiments on a
large collection of graphs show that G 3 is substantially faster than
GPA+ROMA while computing matchings of comparable weight.