# Find subset with minimal sum under constraints

Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function.

Now find $C' \subset C$ with the following constraints:

$$\bigcup C' = M \\ \forall x,y \in C': x \cap y = \emptyset \\ \sum_{x \in C'}w(x) \text{ minimal}$$

In words: Find a subset $C'$ of pair-wise disjunctive pairs over $M$ that covers $M$, with the sum of these pairs being minimal. Any element of $M$ must appear in exactly one pair.

I could not find an efficient algorithmic solution, and I also fail to relate this to any other known (optimization) problem. I was thinking of the subset sum problem, but I don't see any relation.

So the questions is: Can you find an efficient algorithm to find $C'$? A good approximation might also be sufficient. If not, can you reduce this to any other known computer science problem?

• The weight function is completely arbitrary. Dec 10, 2013 at 0:53
• oh, that was not clear from the question - this makes more sense.
– AJed
Dec 10, 2013 at 0:55