Suppose you have a set of objects *X* and a scoring function *f* (in which order does not matter; *f(x,y) = f(y,x)*) which works in the following way.


* Passing a viable pair of these objects to the function will return a real number between, say, 0 and 100.
* Pairing an object to itself will return 101. Think of this as not pairing at all.
* Pairing an unviable pair of these objects will return 203.


In other words, good pair score < bad pair score < no pair score < unviable pair score.


Evaluating *f* on any pair of objects *x,y* takes an equal amount of time.


How do you pair up objects in *X* to minimise the total sum of the scorings, and thereby create an optimal pairing of the objects in the set, in the most efficient way possible?


OR


Assuming we have a function *g* that takes *X* and returns an acceptable threshold, *g(X)*, what is the most efficient way to find a pairing on *X* with a score that is less than *g(X)* (assuming such a pairing is possible).


That is to say, the pairing doesn't need to be absolutely perfect, we're just looking for something that is "pretty good".



Pairing optimisation w.r.t. a given function, or at least close to optimised
If you negate the function, this is a [maximum weight matching](https://en.wikipedia.org/wiki/Maximum_weight_matching) problem in an undirected graph where each object is a node, and there are polynomial algorithms for both exact and approximate solutions.


