# 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.