I see that Blossom algorithm can be used to solve the unweighted version of this problem, and I know that this problem can also be reduced to an LP problem (but with exponential numbers of constraints). Is there a way to solve it in polynomial time?
Yes, the Blossom algorithm for computing maximum unweighted general matchings can be used in a primal-dual algorithm for maximum weighted general matchings (this is a general technique; the Hungarian algorithm is the bipartite equivalent). There's an implementation called Blossom V due to Vladimir Kolmogorov.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With