4
$\begingroup$

Background:

I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:

https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java

The original Python implementation was written by Joris van Rantwijk and the papers he based it on are referenced on his website.

Unfortunately the speed is not adequate for my use case, so I'm looking to improve this. I have added some slow tests to the repo that I will use to measure the performance improvements.

I have further done some research and came up with the following three options to improve performance:

  • Parallelizing Edmonds Blossom, in particular reference is this implementation
  • Variable Dual Updates and the use of Priority Queues as described in Blossom V

Based on the Blossom V paper I'm expecting at least improvements in the order of one or two magnitudes. The reference to the parallel approach is unfortunately no longer available.

Questions:

Now before I get started on in-depth reading and more coding I have some questions that I hope will help me channel my efforts:

  1. Are there any other algorithmic / implementation improvements available to increase performance significantly?
  2. Are there any papers available on parallelizing the algorithm?
  3. I want to do iterative improvements, do you see any reason why I can not add the suggested improvements independently?
  4. What is the best order to add the improvements? What approach has the most value (complexity of implementation vs speed improvement) in your opinion (assuming ~10 cores) and why?
  5. Is there code refactoring / separation you would recommend doing before starting on optimization?

Disclaimer / Misc:

I'm a big believer in Open Source and will keep the repository up with all the improvements I am making to it!

Note: There is also a JavaScript port available here. However not as clean as the Python or Java version.

Edit:

Found a great paper on the Blossom V performance and where to best add parallelization here. That somewhat answers question (2).

I'm now wondering if I should start from scratch and just implement Blossom V.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.