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
