This project is focused on developing an implementation of the Kolmogorov's Blossom V algorithm for minimum weight perfect matching, which is a known problem of combinatorial optimization. Adding this algorithm to the library will extend its support of matchings and make the next step towards implementing other algorithms requiring this one as a subroutine.
The project is divided into following parts:
- developing core part of the algorithm.
- developing fractional matching initialization for a significantly better running time in practice.
- writing benchmark tests, comparing the running time with other algorithms in the area.
- working on code optimizations and extensions of the algorithm.
This project has 2 optional tasks: the price-and-repair technique for better running time on dense graphs, and a minimum cost flow algorithm, which in the context of this project can be used for optimal dual updates.