1
$\begingroup$

Sorry, the title is bad because I don't even know what to call this problem.

I have a set of n objects {obj_0, obj_1, ......, obj_(n-1)}, where n is an even number.

Any two objects can be paired together to produce an output score. So for instance, you might take obj_j and obj_k, and pair them together giving a score of S_j,k. All scores are independent, so the previous example doesn't tell you anything about what the score for combining obj_j and obj_i, S_j,i might be.

There is no ordering in the combination, so S_j,i and S_i,j are the same.

All scores for all pairing possibilities are known.

The whole set of objects is to be taken and organised into pairs (leaving no objects unpaired). The total score, S_tot is the sum of all scores of individual pairs.

What's the most efficient way to find the score-maximising pairing configuration for a large set of such objects? (does this problem have a name?)

Is there a method which works with the version of this problem where objects are grouped into triplets?

$\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.