I'm exploring some applications of perfect matching and I would like some input. I have found many applications in chemistry (storing information, estimating bond lengths, estimating resonance energy, etc). However, I would like to learn more about its applications in other domains - specifically in the "real world" (by that I mean something relatively widely useful instead of confined to a very strict vertical like a branch of quantum mechanics or graph theory). Thank you in advance!
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ There has been a lot of work on kidney transplant matching. In the kidney donation system, if you need kidney, and, say, your sister is willing to donate you a kidney, but you turn out not to be a compatible match with her, there are very often situations where your sister's kidney could be a viable transplant for another patient, whose donor's kidney can be a viable transplant for you. Of course, the donation chain can be even longer. Moreover, there are many complicating factors like how urgently someone needs the transplant. $\endgroup$– Yoav KallusCommented Jul 13, 2017 at 23:08
-
2$\begingroup$ The TSP is used in the "real world" quite a bit, and still the best general approximation employs the min-weight perfect matching at a key step. $\endgroup$– Joseph O'RourkeCommented Jul 13, 2017 at 23:13
-
$\begingroup$ Pairing passengers in ridesharing systems like Lyft Line and UberPool can be treated as a maximum matching problem. I don't have any academic references, but it's alluded to here: eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51 $\endgroup$– Chris ElionCommented Jul 14, 2017 at 3:33
-
$\begingroup$ These are all great! Thank you very much! $\endgroup$– Aidan KehoeCommented Jul 14, 2017 at 20:21
-
$\begingroup$ @YoavKallus I've seen some work on kidney exchange, but I do not recall perfect matchings playing a role there. $\endgroup$– Michael GreineckerCommented Nov 27, 2017 at 15:46
|
Show 1 more comment
5 Answers
$\begingroup$
$\endgroup$
Perfect matching is used in combinatorial optimisation / constraint satisfaction for the AllDifferent constraint. Given a set of variables $x_1, \dots, x_n$ with domains $X_1, \dots, X_n \subset A$ finite sets, $AllDifferent(x_1, \dots, x_n)$ is true iff $x_i \neq x_j$ for all $i \neq j$. This turns into a matching problem between the variables $x_i$ and elements of $A$: we put an edge $(i,a)$ if $a \in X_i$, which results in a bipartite graph. Finding an assignment to the variables is equivalent to finding a matching. In reality we don't just want to find an assignment but we want to remove all items from the domains $X_i$ that can never lead to a valid assignment. For example if the domains are $X_1 = \{1,2\}, X_2 = \{1,2\}, X_3 = \{1,2,3\}$ then we can remove $1$ and $2$ from $X_3$ because they can never lead to a valid assignment. You can quickly find all these removeable elements with a variant of the bipartite matching algorithm.
See also Propagation Algorithms for the Alldifferent Constraint.
$\begingroup$
$\endgroup$
like to learn more about its applications in other domains - specifically in the "real world" (by that I mean something relatively widely useful instead of confined to a very strict vertical like a branch of quantum mechanics or graph theory)
Just to add an example fitting your request (no chemistry here, and there are more complicated game-theoretic examples, but this is pretty much the easiest non-trivial example): perfect matchings are a concept without which certain perfect-information games could not conveniently be analyzed. Easy example: for any finite simple undirected graph G (not necessarily connected, but the game will perforce unfold in one connected component only), consider the two-player game between player A and B with precisely the following rules: A moves first by choosing an arbitrary vertex v of G. Henceforth, the players must alternatingly choose a vertex-not-yet-chosen, each choice being arbitrary except that the vertex chosen must be adjacent in G to the vertex previously chosen by the other player. (In particular, the two players collaborate in choosing a graph-theoretic path in G.) The player which first cannot legally choose any vertex looses. It can be proved that
- if G has a perfect matching, then there exists a winning strategy for B (for B to actually win against a strong player A if B does not know a perfect matching might not be easy for B though; for complicated G this is not a no-brainer)
- if B knows (e.g. by having calculated one M beforehand, or by having been given one by an oracle) a perfect matching M of G, then B can use M to always win, no matter how intelligent A is
- if G does not have a perfect matching, then there exists a winning strategy for A (sort-of-symmetrially to above, for A to then actually win against a strong player B, if A does not know a maximum matching to use as a guide, might still not be easy though; for complicated G this is not a no-brainer).
- if A knows (e.g. by having calculated one M beforehand, or by having been given one by an oracle) a maximum (then necessarily non-perfect) matching M of G, then A can use M to always win, no matter how intelligent B is.
Remark. In both cases above, if the player having the winning strategy has a perfect (resp. maximum) matching handy, they will win even if they announce to the opponent which matching it is that they use as their guide. This is another twist, and does not go without saying. (There are games where there exists such a "road-map to victory" but the winning player has to keep it secret for the road-map to work. Fancifullily put, the perfect (respectively maximum) matching makes it possible to win against an opponent which is not only infinitely-intelligent, but also clairvoyant.
Relevance to your question. It seems that without the abstract concept "(perfect) matching", analyzing this game would be more difficult, so this is an application of the concept of perfect matching.
answered Jul 14, 2017 at 14:49
$\begingroup$
$\endgroup$
Topological codes in a quantum computer are decoded by a miminum-weight perfect matching algorithm, as discussed for example in this article. We don't yet have an operational quantum computer, but this may well become a "real-world" application of perfect matching in the next decade.
answered Nov 27, 2017 at 12:40
$\begingroup$
$\endgroup$
You may want to check a paper about matching at arXiv:1805.00214.
Even though the general problems are NP-complete or intractable in layman's terms, one may want to find triples or quadruples in some special cases. Such algorithms run in $\mathcal{O}(n \log n)$ time.
$\begingroup$
$\endgroup$
1
Designs of experiments may use matching. Imagine we have 100 female patients and 100 male patients. We want to apply some treatment to both groups to see if there is any difference between the response of male and female patients. But there may be another variable such as age, as an example. Such a variable is called a confounding variable and there are prety complicated ways to define a confounding variable, such as propensity score, etc.
Now we want to pair male and female patients so that the sum of absolute values of differences in male and female patients within each pair is the smallest. That would lead to bipartite matching.
We may have 300 patients, age would be the confounding variable, and we may want to partition them to pairs with ages as close as possible, we mean the sum of absolute values of differences of ages in each pair. The first patient in each pair may recieve treatment A, the second one may recieves reatment B. That would lead to nonbipartite matching.
What if we want to form triples to be able to apply placebo (or perhaps the usual treatment instead), treatment A, and treatment B. Even though the general problem is NP-complete or, in layman's terms, intractable. Ask around.
The same would hold for quadruples: placebo, treatment A, treatment B, interaction AB.
Sincerely, Josef
-
$\begingroup$ -1 The example is about an application of the bipartite matching, but I don't see how it applies to the case of a perfect one in the edge-theoretic sense. $\endgroup$ Commented Mar 19, 2023 at 8:47