[Solved]: Find subset with minimal sum under constraints

Problem Detail: 

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?

Asked By : morris4

Answered By : Yuval Filmus

Your problem is known as minimum-weight perfect matching, and can be solved in polynomial time using several different algorithms. One algorithm that can be used is Edmonds' Blossom algorithm. See also Cook and Rohe, who discuss how to implement Blossom.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18799

 Ask a Question

 Download Related Notes/Documents