Given a group of people, where each pair has a val

Question

It's very much like the Assignment Problem, except with a complete undirected graph rather than a bipartite graph.

The dumbest, most brute force-iest solution is something like this:

1. Get all possible configurations of pairs...

   groups = people.combination(2).to_a.combination(people.size/2).to_a

2. ...rejecting all of the configurations that contain the same person more than once.

   groups.reject! { |group| group.flatten.uniq.size < people.size }

3. Then find the configuration with the minimum value.

   groups.min_by { |group| group.inject(0) { |pair| value_for(pair) }

Is there a modification of the Branch and Bound solution for the Assignment Problem that takes into account that, here, the Job and Person are both People?

Could there be another combinatorics problem which more closely resembles what I've presented?

How can I get the best solution without frying my CPU?

Thanks!

Answer 1

This is possible in polynomial time with https://en.wikipedia.org/wiki/Blossom_algorithm#Weighted_matching.