New Iterative Algorithms for Weighted Matching
Alexander Idelberger, Fredrik Manne · 2014
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.