Priority matching
In graph theory, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a graph G = (V, E), and a partition of the vertex-set V into some k subsets, V1, …, Vk, called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from V1; subject to this, it saturates the largest number of vertices from V2; subject to this, it saturates the largest number of vertices from V3; and so on.
Priority matchings were introduced by Alvin Roth, Tayfun Sonmez and Utku Unver[1] in the context of kidney exchange. In this problem, the vertices are patient-donor pairs, and each edge represents a mutual medical compatibility. For example, an edge between pair 1 and pair 2 indicates that donor 1 is compatible with patient 2 and donor 2 is compatible with patient 1. The priority classes correspond to medical priority among patients. For example, some patients are in a more severe condition so they must be matched first. Roth, Sonmez and Unver assumed that each priority-class contains a single vertex, i.e., the priority classes induce a total order among the pairs.
Later, Yasunori Okumura[2] extended the work to priority-classes that may contain any number of vertices. He also showed how to find a priority matching efficiently using an algorithm for maximum-cardinality matching, with a run-time complexity of O(|V||E| + |V|2 log |V|).
Jonathan S. Turner[3] presented a variation of the augmenting path method (Edmonds' algorithm) that finds a priority matching in time O(|V||E|). Later, he found a faster algorithm for bipartite graphs: the algorithm runs in time[4]
- [math]\displaystyle{ O(k |E| \sqrt{|V|} ) }[/math]
See also
- Maximum cardinality matching
- Rank-maximal matching
References
- ↑ Roth, Alvin E.; Sönmez, Tayfun; Utku Ünver, M. (2005-12-01). "Pairwise kidney exchange" (in en). Journal of Economic Theory 125 (2): 151–188. doi:10.1016/j.jet.2005.04.004. ISSN 0022-0531. http://papers.nber.org/papers/w10698.pdf.
- ↑ Okumura, Yasunori (2014-11-01). "Priority matchings revisited" (in en). Games and Economic Behavior 88: 242–249. doi:10.1016/j.geb.2014.10.007. ISSN 0899-8256.
- ↑ Turner, Jonathan (2015-12-28). "Maximium [sic] Priority Matchings". arXiv:1512.08555 [cs.DS].
- ↑ Turner, Jonathan (2015-12-31). "Faster Maximium [sic] Priority Matchings in Bipartite Graphs". arXiv:1512.09349 [cs.DS].
 |  |
