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?

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

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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