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.

Organization

Student

Tymofii Chudakov

Mentors

  • Joris Kinable
  • Dimitrios Michail
close

2018