3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The weight function is completely arbitrary. $\endgroup$ – Yuval Filmus Dec 10 '13 at 0:53
  • $\begingroup$ oh, that was not clear from the question - this makes more sense. $\endgroup$ – AJed Dec 10 '13 at 0:55
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow. Can't believe I didn't see that (M, C) is a graph. Thank you very much. $\endgroup$ – morris4 Dec 10 '13 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.