ABCDEFGHIJKLMNOPQRSTUVWXYZAAABACAD
1
2
Problem ClassNameSupports Ties
Supports MultiInstance
Supports Incomplete ListsSupports One2ManySupports Odd #RoommatesDescriptionReference
3
SRTan-HsuehYNYNYProduces a reduced stable partition in a given instance (arbitrary tie break).https://doi.org/10.1016/0166-218X(93)E0154-Q
4
SRNo-Ties StableNYYNYProduces a stable matching or reports that none exists.https://doi.org/10.1016/0196-6774(85)90033-1
5
SRMaximum StableNNYNYProduces a maximum stable matching by deleting one agent from each odd cycle of a reduced stable partition.https://doi.org/10.1080/00207169108803975
6
SRAll Stable MatchingsNNYNNFinds all (if any) admitted stable matchings through enumeration.https://doi.org/10.1137/0217048
7
SRAll Stable PairsNNYNNFinds all (if any) admitted stable pairs through enumeration.https://doi.org/10.1137/0217048
8
SREgalitarian StableNNYNNProduces an egalitarian stable matching, or reoprts that none exists.https://doi.org/10.1137/0217048
9
SRMinimum RegretNNYNNProduces a minimum regret stable matching, or reports that none exists.https://mitpress.mit.edu/9780262515528/the-stable-marriage-problem/
10
HAPopularYYYYN/AProduces a popular matching or reports that none exists.https://doi.org/10.1137/06067328X
11
HARank-MaximalYYYYN/AProduces a rank-maximal matching.https://doi.org/10.1145/1198513.1198520
12
HAGreedyYYYYN/AProduces a greedy maximum matching.https://www.dcs.gla.ac.uk/~rwi/greedy.pdf
13
HAGenerousYYYYN/AProduces a generous maximum matching.https://www.dcs.gla.ac.uk/~rwi/greedy.pdf
14
HAGreedy-GenerousYYYYN/AProduces a greedy-generous maximum profile.https://www.dcs.gla.ac.uk/~rwi/greedy.pdf
15
HAMinimum CostYYYYN/AProduces a minimum cost maximum matching.Folklore
16
HANaiveYYYYN/AProduces a matching using the random serial dictatorship mechanism.Folklore
17
HAPopular PairsYYYNN/AFinds all admitted popular pairs.https://doi.org/10.1007/s10878-009-9287-9
18
HAVisualise Switching GraphYNYYN/AVisualises the switching graph for popular matchings.https://doi.org/10.1007/s10878-009-9287-9
19
HAMaximum Cardinality Pareto OptimalNYYYN/AProduces a maximum cardinality Pareto optimal matching.https://doi.org/10.1007/978-3-540-30551-4_3
20
HANumber of Popular MatchingsNYYNN/AComputes the number of popular matchings admitted by the instance.https://doi.org/10.1007/s10878-009-9287-9
21
HAMinimum Cost Maximum Cardinality PopularNYYNN/AProduces a maximum cardinality popular matching with minimum cost.https://doi.org/10.1007/s10878-009-9287-9
22
HARank-Maximal PopularNYYNN/AProduces a rank-maximal popular matching or reports that none exists.https://doi.org/10.1007/s10878-009-9287-9
23
HAGenerous Maximum Cardinality PopularNYYNN/AProduces a maximum cardinality popular matching with generous profile.https://doi.org/10.1007/s10878-009-9287-9
24
HAPopular Uniform at RandomNYYNN/AProduces a popular matching uniform at random, or reports that none exists.https://doi.org/10.1007/s10878-009-9287-9
25
HAEnumerate all Popular MatchingsNNYNN/AFinds all admitted popular matchings.https://doi.org/10.1007/s10878-009-9287-9
26
HRKiraly One-Sided TiesYYYYN/AProduces an approximation for a maximum stable matching for instances with complete or incomplete lists and ties only on the hospital side.https://doi.org/10.1007/978-3-540-87744-8_52
27
HRKiraly Two-Sided TiesYYYYN/AProduces an approximation for a maximum stable matching for instances with complete or incomplete lists and ties on both sides.https://doi.org/10.3390/a6030471
28
HRSuper StableYNYYN/AProduces a super-stable matching, or reports that none exists.https://doi.org/10.1007/3-540-44985-X_24
29
HRStrongly StableYNYNN/AProduces a strongly stable matching in the SMTI context, or reports that none exists.https://doi.org/10.1007/3-540-36494-3_39
30
HRNo-Ties StableNYYYN/AProduces the resident-optimal stable matching.https://doi.org/10.2307/2312726
31
HRMaximum PopularNNYNN/AProduces a maximum popular matching in the SMI context.https://doi.org/10.1016/j.ic.2012.10.012
32
HRAll Stable Matchings (Rotations)NNNNN/AFinds all stable matchings via rotation elimination in the SM context (requires complete preference lists).https://doi.org/10.1137/0216010
33
HRAll Stable Matchings (Breakmarriage)NNNNN/AFinds all stable matchings using Algorithm Breakmarriage in the SM context (requires complete preference lists).https://doi.org/10.1145/362619.362631
34
HRAll Stable PairsNNNNN/AFinds all stable pairs through enumeration in the SM context (requires complete preference lists).https://doi.org/10.1137/0216010
35
HREgalitarian StableNNNNN/AProduces an egalitarian stable matching in the SM context (requires complete preference lists).https://doi.org/10.1145/28869.28871
36
HRMinimum RegretNNNNN/AProduces a minimum regret stable matching in the SM context (requires complete preference lists).https://doi.org/10.1137/0216010
37
HRMinimum Resident RegretNNNNN/AProduces a stable matching in the SM context with minimum resident regret (requires complete preference lists).https://doi.org/10.1137/0216010
38
HRMinimum Hospital RegretNNNNN/AProduces a stable matching in the SM context with minimum hospital regret (requires complete preference lists).https://doi.org/10.1137/0216010
39
SPACost-Optimal One-sidedYYYN/AN/AProduces a minimum cost maximum matching considering only student preferences.https://doi.org/10.1007/978-3-319-19315-1_19
40
SPAGreedy One-SidedYYYN/AN/AProduces a greedy maximum matching considering only student preferences.https://doi.org/10.1007/978-3-319-19315-1_19
41
SPAGenerous One-SidedYYYN/AN/AProduces a generous maximum matching considering only student preferences.https://doi.org/10.1007/978-3-319-19315-1_19
42
SPAStudent-Optimal StableNYYN/AN/AProduces the student-optimal stable matching.https://doi.org/10.1016/j.jda.2006.03.006
43
SPALecturer-Optimal StableNYYN/AN/AProduces the lecturer-optimal stable matching.https://doi.org/10.1016/j.jda.2006.03.006
44
45
46
AcronymsGeneral Reference
47
EGSExtended Gale Shapley Algorithm
https://www.dcs.gla.ac.uk/research/algorithms/AMUP
48
HAHouse Allocation Problem
49
HATHouse Allocation Problem with Ties
50
HRTHospitals/Residents Problem with Ties
51
MAX HROSTMaximum Cardinality Stable Matching in the Hospitals/Residents Problem with one sided Ties
52
MAX HRTMaximum Cardinality Stable Matching in the Hospitals/Residents Problem with Ties
53
SMStable Marriage Problem
54
SMTStable Marriage Problem with Ties
55
SMIStable Marriage Problem with Incomplete Lists
56
SMTIStable Marriage Problem with Ties and Incomplete Lists
57
SRStable Roommates Problem
58
SRIStable Roommates Problem with Incomplete lists
59
SPAStudent-Project Allocation Problem
60
SPA-SStudent-Project Allocation with Lecturer preferences over Students
61
SPA-STStudent-Project Allocation with Lecturer preferences over Students and Ties
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100