1128:
If the doctor is unemployed or has a less-preferred assignment, the doctor accepts the offer (and resigns from their other assignment if it exists). The process always terminates, because each doctor and hospital interact only once. When it terminates, the result is a stable matching, the one that assigns each hospital to its best match and that assigns all doctors to their worst matches. An algorithm that swaps the roles of the doctors and hospitals (in which unemployed doctors send a job applications to their next preference among the hospitals, and hospitals accept applications either when they have an unfilled position or they prefer the new applicant, firing the doctor they had previously accepted) instead produces the stable matching that assigns all doctors to their best matches and each hospital to its worst match.
3216:
of stable matchings, each participant is matched to the median element of the multiset of their matches from the given matchings. For an even set of stable matchings, this can be disambiguated by choosing the assignment that matches each doctor to the higher of the two median elements, and each hospital to the lower of the two median elements. In particular, this leads to a definition for the median matching in the set of all stable matchings. However, for some instances of the stable matching problem, finding this median of all stable matchings is
2781:
total weight of the lower matching. By the correspondence between stable matchings and lower sets of rotations, the total weight of any matching is then equal to the total weight of its corresponding lower set, plus the weight of the bottom element of the lattice of matchings. The problem of finding the minimum or maximum weight stable matching becomes in this way equivalent to the problem of finding the minimum or maximum weight lower set in a partially ordered set of polynomial size, the partially ordered set of rotations.
2303:
matching can be obtained by changing the given matching by rotations downward in the partial ordering, choosing arbitrarily which rotation to perform at each step, until reaching the bottom element, and listing the rotations used in this sequence of changes. The stable matching associated with any lower set of rotations can be obtained by applying the rotations to the bottom element of the lattice of stable matchings, choosing arbitrarily which rotation to apply when more than one can apply.
2299:
are separately the higher matching for the same rotation, then so is their meet. It follows that for any rotation, the set of stable matchings that can be the higher of a pair connected by the rotation has a unique lowest element. This lowest matching is join irreducible, and this gives a one-to-one correspondence between rotations and join-irreducible stable matchings.
140:
preferences for which hospital they would like to work at (for instance based on which cities they would prefer to live in), and the hospitals each have preferences for which doctors they would like to work for them (for instance based on specialization or recommendations). The goal is to find a matching that is
2298:
whose edges alternate between the two matchings. Equivalently, the rotation can be described as the set of changes that would need to be performed to change the lower of the two matchings into the higher one (with lower and higher determined using the partial order). If two different stable matchings
1127:
gives a process for constructing stable matchings, that can be described as follows: until a matching is reached, the algorithm chooses an arbitrary hospital with an unfilled position, and that hospital makes a job offer to the doctor it most prefers among the ones it has not already made offers to.
383:
the other. The same comparison operation can be defined in the same way for any two sets of elements, not just doctors and hospitals. The choice of which of the two sets of elements to use in the role of the doctors is arbitrary. Swapping the roles of the doctors and hospitals reverses the ordering
139:
In its simplest form, an instance of the stable matching problem consists of two sets of the same number of elements to be matched to each other, for instance doctors and positions at hospitals. Each element has a preference ordering on the elements of the other type: the doctors each have different
3215:
and similarly by assigning each hospital the median of the three doctors matched to it. More generally, any set of an odd number of elements of any distributive lattice (or median graph) has a median, a unique element minimizing its sum of distances to the given set. For the median of an odd number
1115:
to any other partner in any stable matching. This contradiction shows that assigning all doctors to their best matches gives a matching. It is a stable matching, because any unstable pair would also be unstable for one of the matchings used to define best matches. As well as assigning all doctor to
2877:
defines the regret of a participant in a stable matching to be the distance of their assigned match from the top of their preference list. He defines the regret of a stable matching to be the maximum regret of any participant. Then one can find the minimum-regret stable matching by a simple greedy
2780:
From the weights on pairs of elements, one can assign weights to each rotation, where a rotation that changes a given stable matching to another one higher in the partial ordering of stable matchings is assigned the change in weight that it causes: the total weight of the higher matching minus the
2302:
If the rotations are given the same partial ordering as their corresponding join-irreducible stable matchings, then
Birkhoff's representation theorem gives a one-to-one correspondence between lower sets of rotations and all stable matchings. The set of rotations associated with any given stable
2752:
from a given instance of stable matching, and provides a concise representation to the family of all stable matchings, which can for some instances be exponentially larger when listed explicitly. This allows several other computations on stable matching instances to be performed efficiently.
2597:
of counting the number of stable matchings of a given instance. From the equivalence between lattices of stable matchings and arbitrary finite distributive lattices, it follows that this problem has equivalent computational complexity to counting the number of elements in an arbitrary finite
2154:
of an associated partial order. In the general form of
Birkhoff's theorem, this partial order can be taken as the induced order on a subset of the elements of the lattice, the join-irreducible elements (elements that cannot be formed as joins of two other elements). For the lattice of stable
1715:
in which there is a unique minimum element and a unique maximum element, in which every two elements have a unique least element greater than or equal to both of them (their join) and every two elements have a unique greatest element less than or equal to both of them (their meet).
3150:
2878:
algorithm that starts at the bottom element of the lattice of matchings and then repeatedly applies any rotation that reduces the regret of a participant with maximum regret, until this would cause some other participant to have greater regret.
1119:
Symmetrically, assigning all doctors to their worst matches and assigning all hospitals to their best matches gives another stable matching. In the partial order on the matchings, it is less than all other stable matchings.
2150:, with intersection and union as the meet and join operations, and with the relation of being a subset as the comparison operation for the associated partial order. More specifically, these sets can be taken to be the
1837:
because it was defined to give each doctor their preferred choice, and because these preferences of the doctors are how the ordering on matchings is defined. It is below any other matching that is also above both
1878:, because any such matching would have to give each doctor an assigned match that is at least as good. Therefore, it fits the requirements for the join operation of a lattice. Symmetrically, the operation
2046:
2126:
3155:
For the lattice of stable matchings, this median can instead be taken element-wise, by assigning each doctor the median in the doctor's preferences of the three hospitals matched to that doctor in
1599:
are stable. There cannot be a pair of a doctor and hospital who prefer each other to their match, because the same pair would necessarily also be an unstable pair for at least one of
3003:
2860:
2486:
Beyond being a finite distributive lattice, there are no other constraints on the lattice structure of stable matchings. This is because, for every finite distributive lattice
2338:
of elements of a given stable matching instance belongs to at most two rotations: one rotation that, when applied to the lower of two matchings, removes other assignments to
2689:
125:
2583:
1902:
1769:
1697:
1597:
1542:
1424:
1325:
1226:
2995:
2471:
2814:
2722:
1795:
1743:
1671:
1571:
1516:
1450:
1398:
1256:
1200:
1073:
968:
923:
898:
813:
670:
644:
618:
529:
503:
435:
241:
151:
In general, there may be many different stable matchings. For example, suppose there are three doctors (A,B,C) and three hospitals (X,Y,Z) which have preferences of:
2834:
2435:
2408:
2336:
381:
215:
3573:; Gharan, Shayan Oveis; Weber, Robbie (2018), "A simply exponential upper bound on the maximum number of stable matchings", in Diakonikolas, Ilias; Kempe, David;
2761:
If each pair of elements in a stable matching instance is assigned a real-valued weight, it is possible to find the minimum or maximum weight stable matching in
3213:
3193:
3173:
2954:
2934:
2914:
2647:
2627:
2544:
2524:
2504:
2376:
2356:
2288:
2268:
2244:
2224:
2204:
2184:
1969:
1949:
1929:
1876:
1856:
1835:
1815:
1637:
1617:
1490:
1470:
1365:
1345:
1296:
1276:
1174:
1154:
1113:
1093:
1048:
1028:
1008:
988:
943:
873:
853:
833:
788:
768:
748:
728:
708:
592:
572:
552:
477:
457:
409:
361:
341:
321:
301:
281:
261:
1116:
their best matches, it assigns all hospitals to their worst matches. In the partial ordering on the matchings, it is greater than all other stable matchings.
85:
Every finite distributive lattice can be represented as a lattice of stable matchings. The number of elements in the lattice can vary from an average case of
770:
in a stable matching, and define the worst match analogously. Then no two elements can have the same best match. For, suppose to the contrary that doctors
74:
describing the changes between adjacent stable matchings in the lattice. The family of all rotations and their partial order can be constructed in
1452:, for regardless of which of the two doctors is preferred by the hospital, that doctor and hospital would form an unstable pair in whichever of
1907:
Because they are defined using an element-wise minimum or element-wise maximum in the preference ordering, these two operations obey the same
3751:
2792:
in which the goal is to find a subset of vertices of optimal weight with no outgoing edges. The optimal lower set is an optimal closure of a
176:
The lattice of stable matchings organizes this collection of solutions, for any instance of stable matching, giving it the structure of a
78:, leading to polynomial time solutions for other problems on stable matching including the minimum or maximum weight stable matching. The
387:
Then this ordering gives the matchings the structure of a partially ordered set. To do so, it must obey the following three properties:
144:: no pair of a doctor and a hospital prefer each other to their assigned match. Versions of this problem are used, for instance, by the
1426:
are matchings. It is not possible, for instance, for two doctors to have the same best choice and be matched to the same hospital in
1977:
2057:
2862:
in the partial order. The closure problem can, in turn, be solved in polynomial time by transforming it into an instance of the
2378:
and instead assigns them to each other, and a second rotation that, when applied to the lower of two matchings, removes pair
3536:
2143:
59:
2691:. In a stable marriage instance chosen to maximize the number of different stable matchings, this number can be at least
3827:
145:
3277:
2887:
2250:
of the partial order of stable matchings.) Then the set of pairs of elements that are matched in one but not both of
1371:(The same operations can be defined in the same way for any two sets of elements, not just doctors and hospitals.)
3498:
3453:
3496:(1987), "Every finite distributive lattice is a set of stable matchings for a small stable marriage instance",
3145:{\displaystyle m(P,Q,R)=(P\wedge Q)\vee (P\wedge R)\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)\wedge (Q\vee R).}
3825:
Teo, Chung-Piaw; Sethuraman, Jay (1998), "The geometry of fractional stable matchings and its applications",
676:
For stable matchings, all three properties follow directly from the definition of the comparison operation.
3789:
3493:
283:: either they have the same assigned hospital in both matchings, or they are assigned a better hospital in
3661:
2839:
1124:
685:
79:
47:
description of the family of all solutions to the problem. It was originally described in the 1970s by
1911:
obeyed by the minimum and maximum operations on linear orderings: for every three different matchings
3625:
3417:
3378:
2155:
matchings, the elements of the partial order can instead be described in terms of structures called
3903:
2774:
2594:
3264:
2652:
88:
3908:
40:
2793:
2549:
1881:
1748:
1676:
1576:
1521:
1403:
1304:
1205:
2959:
2440:
2206:
are comparable and have no third stable matching between them in the partial order. (That is,
2799:
2694:
2506:, there exists a stable matching instance whose lattice of stable matchings is isomorphic to
1774:
1722:
1650:
1550:
1495:
1429:
1377:
1235:
1179:
649:
623:
597:
508:
482:
414:
384:
of every pair of elements, but does not otherwise change the structure of the partial order.
220:
194:
67:
2819:
3884:
3848:
3812:
3774:
3729:
3682:
3646:
3604:
3557:
3521:
3476:
3438:
3324:
3287:
2863:
2729:
2413:
2381:
2309:
2291:
2132:
1704:
366:
200:
177:
36:
8:
3451:
Blair, Charles (1984), "Every finite distributive lattice is a set of stable matchings",
3415:
Irving, Robert W.; Leather, Paul (1986), "The complexity of counting stable marriages",
2777:. An alternative, combinatorial algorithm is possible, based on the same partial order.
2410:
from the matching and finds other assignments for those two elements. Because there are
1053:
948:
903:
878:
793:
3706:
3582:
3198:
3178:
3158:
2939:
2919:
2899:
2766:
2632:
2612:
2529:
2509:
2489:
2361:
2341:
2273:
2253:
2229:
2209:
2189:
2169:
1954:
1934:
1914:
1861:
1841:
1820:
1800:
1622:
1602:
1475:
1455:
1350:
1330:
1281:
1261:
1159:
1139:
1098:
1078:
1033:
1013:
993:
973:
928:
858:
838:
818:
773:
753:
733:
713:
693:
577:
557:
537:
462:
442:
394:
346:
326:
306:
286:
266:
246:
48:
3861:
Cheng, Christine T. (2010), "Understanding the generalized median stable matchings",
3803:
3674:
3512:
3467:
3356:
3351:
3273:
2247:
1327:, each doctor gets their worst choice among the two hospitals they are matched to in
3765:
3337:
Peranson, E.; Randlett, R. R. (June 1995), "The NRMP matching algorithm revisited",
1258:, each doctor gets their best choice among the two hospitals they are matched to in
3872:
3836:
3798:
3760:
3742:
3715:
3670:
3634:
3592:
3574:
3545:
3507:
3462:
3426:
3387:
3373:
3346:
3310:
2602:
in an arbitrary partially ordered set. Computing the number of stable matchings is
1908:
82:
can be used to construct two special lattice elements, its top and bottom element.
44:
28:
3787:
Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), "Medians in median graphs",
3746:
3391:
1518:, the hospitals must also be matched. The same reasoning applies symmetrically to
3880:
3844:
3808:
3770:
3725:
3678:
3642:
3600:
3553:
3517:
3472:
3434:
3320:
3283:
2785:
2762:
2749:
2603:
1708:
166:
The doctors get their first choice and the hospitals get their third: AY, BZ, CX.
128:
75:
2546:
elements, then it can be realized using a stable matching instance with at most
70:. The elements of this set can be given a concrete structure as rotations, with
43:. For a given instance of the stable matching problem, this lattice provides an
2789:
2770:
3876:
3315:
2796:
that has the elements of the partial order as its vertices, with an edge from
2146:
states that any finite distributive lattice can be represented by a family of
193:
The lattice of stable matchings is based on the following weaker structure, a
3897:
1700:
172:
The hospitals get their first choice and the doctors their third: AZ, BX, CY.
3596:
2997:
that lies on a shortest path between any two of them. It can be defined as:
3863:
3701:
3620:
3489:
3260:
2893:
52:
3840:
3360:
3570:
3301:
Hwang, J. S. (1982), "The lattice of stable marriages and permutations",
3266:
Mariages stables et leurs relations avec d'autres problèmes combinatoires
2748:
The family of rotations and their partial ordering can be constructed in
2725:
2295:
71:
20:
3720:
3272:(in French), Montréal, Quebec: Les Presses de l'Université de Montréal,
3659:
Vande Vate, John H. (1989), "Linear programming brings marital bliss",
2147:
1712:
197:
whose elements are the stable matchings. Define a comparison operation
3623:(1987), "Three fast algorithms for four problems in stable marriage",
2737:
2599:
2151:
63:
24:
3704:(1987), "An efficient algorithm for the "optimal" stable marriage",
3638:
3579:
Proceedings of the 50th
Symposium on Theory of Computing (STOC 2018)
3549:
3430:
2649:
hospitals, the average number of stable matchings is asymptotically
1492:
they are not already matched in. Because the doctors are matched in
127:
to a worst-case of exponential. Computing the number of elements is
3587:
2784:
This optimal lower set problem is equivalent to an instance of the
2609:
In a uniformly-random instance of the stable marriage problem with
3217:
2294:
of their sets of matched pairs) is called a rotation. It forms a
3534:
Pittel, Boris (1989), "The average number of stable matchings",
162:
There are three stable solutions to this matching arrangement:
323:. If the doctors disagree on which matching they prefer, then
2888:
Median graph § Distributive lattices and median algebras
2041:{\displaystyle P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)}
750:
most prefers, among all the elements that can be matched to
2121:{\displaystyle P\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)}
1298:(if these differ) and each hospital gets its worst choice.
3581:, Association for Computing Machinery, pp. 920–925,
3488:
2593:
The lattice of stable matchings can be used to study the
1367:(if these differ) and each hospital gets its best choice.
945:(which must exist by the definition of the best match of
3303:
Journal of the
Australian Mathematical Society, Series A
16:
Distributive lattice whose elements are stable matchings
2756:
2956:(here, stable matchings) have a unique median element
2526:. More strongly, if a finite distributive lattice has
3699:
3201:
3181:
3161:
3006:
2962:
2942:
2922:
2902:
2842:
2822:
2802:
2697:
2655:
2635:
2615:
2552:
2532:
2512:
2492:
2443:
2416:
2384:
2364:
2344:
2312:
2276:
2256:
2232:
2212:
2192:
2172:
2060:
1980:
1957:
1937:
1917:
1884:
1864:
1844:
1823:
1803:
1777:
1751:
1725:
1679:
1653:
1625:
1605:
1579:
1553:
1524:
1498:
1478:
1458:
1432:
1406:
1380:
1353:
1333:
1307:
1284:
1264:
1238:
1208:
1182:
1162:
1142:
1101:
1081:
1056:
1036:
1016:
996:
976:
951:
931:
906:
881:
861:
841:
821:
796:
776:
756:
736:
716:
696:
652:
626:
600:
580:
560:
540:
511:
485:
465:
445:
417:
397:
369:
349:
329:
309:
289:
269:
249:
223:
203:
169:
All participants get their second choice: AX, BY, CZ.
91:
1176:
for the same input, one can form two more matchings
3207:
3187:
3167:
3144:
2989:
2948:
2928:
2908:
2854:
2828:
2808:
2716:
2683:
2641:
2621:
2577:
2538:
2518:
2498:
2465:
2429:
2402:
2370:
2350:
2330:
2282:
2262:
2238:
2218:
2198:
2178:
2120:
2040:
1963:
1943:
1923:
1896:
1870:
1850:
1829:
1809:
1789:
1763:
1737:
1691:
1665:
1631:
1611:
1591:
1565:
1536:
1510:
1484:
1464:
1444:
1418:
1392:
1359:
1339:
1319:
1290:
1270:
1250:
1220:
1194:
1168:
1148:
1107:
1087:
1067:
1042:
1022:
1002:
982:
962:
937:
917:
892:
867:
847:
827:
807:
782:
762:
742:
722:
702:
664:
638:
612:
586:
566:
546:
523:
497:
471:
451:
429:
403:
375:
355:
335:
315:
295:
275:
255:
235:
209:
119:
3786:
3569:
148:to match American medical students to hospitals.
3895:
3336:
2892:The elements of any distributive lattice form a
2131:Therefore, the lattice of stable matchings is a
710:of a stable matching instance to be the element
3747:"A ternary operation in distributive lattices"
2138:
1904:fits the requirements for the meet operation.
3824:
3752:Bulletin of the American Mathematical Society
3414:
2773:of the partial order of rotations, or to the
2588:
2160:
188:
3741:
2166:Suppose that two different stable matchings
900:. Then, in the stable matching that matches
3615:
3613:
2765:. One possible method for this is to apply
2743:
243:if and only if all doctors prefer matching
3658:
2896:, a structure in which any three elements
2476:
679:
3802:
3764:
3719:
3586:
3511:
3466:
3350:
3314:
3291:. See in particular Problem 6, pp. 87–94.
2881:
2598:distributive lattice, or to counting the
155:A: YXZ B: ZYX C: XZY
62:, this lattice can be represented as the
3619:
3610:
3372:
3255:
3253:
2874:
3366:
3251:
3249:
3247:
3245:
3243:
3241:
3239:
3237:
3235:
3233:
3896:
3695:
3693:
3691:
3533:
2736:(significantly smaller than the naive
3860:
3854:
3527:
3450:
3300:
3259:
1642:
1131:
3537:SIAM Journal on Discrete Mathematics
3444:
3410:
3408:
3406:
3404:
3402:
3400:
3294:
3230:
2757:Weighted stable matching and closure
690:Define the best match of an element
534:For every three different matchings
3688:
3482:
3330:
2740:bound on the number of matchings).
1010:would be an unstable pair, because
13:
3828:Mathematics of Operations Research
3818:
3780:
3735:
3700:Irving, Robert W.; Leather, Paul;
3652:
3563:
2855:{\displaystyle \alpha \leq \beta }
1711:is defined as a partially ordered
479:, it cannot be the case that both
439:For every two different matchings
158:X: BAC Y: CBA Z: ACB
146:National Resident Matching Program
14:
3920:
3492:; Irving, Robert; Leather, Paul;
3397:
2869:
2144:Birkhoff's representation theorem
1797:is greater than or equal to both
363:are incomparable: neither one is
60:Birkhoff's representation theorem
3352:10.1097/00001888-199506000-00008
3766:10.1090/S0002-9904-1947-08864-9
3499:Journal of Combinatorial Theory
3454:Journal of Combinatorial Theory
2788:, a problem on vertex-weighted
2481:
1136:Given any two stable matchings
217:on the stable matchings, where
3136:
3124:
3118:
3106:
3100:
3088:
3082:
3070:
3064:
3052:
3046:
3034:
3028:
3010:
2984:
2966:
2460:
2447:
2397:
2385:
2325:
2313:
2115:
2103:
2097:
2085:
2079:
2067:
2035:
2023:
2017:
2005:
1999:
1987:
1719:In the case of the operations
835:as their best match, and that
1:
3392:10.1215/S0012-7094-37-00334-X
3223:
2437:pairs of elements, there are
134:
3804:10.1016/0166-218X(84)90096-9
3790:Discrete Applied Mathematics
3675:10.1016/0167-6377(89)90041-2
3513:10.1016/0097-3165(87)90037-9
3468:10.1016/0097-3165(84)90056-6
2684:{\displaystyle e^{-1}n\ln n}
1707:. In this context, a finite
183:
120:{\displaystyle e^{-1}n\ln n}
7:
3662:Operations Research Letters
2161:Irving & Leather (1986)
2139:Representation by rotations
33:lattice of stable matchings
10:
3925:
2885:
2589:Number of lattice elements
683:
189:Partial order on matchings
3877:10.1007/s00453-009-9307-2
3626:SIAM Journal on Computing
3418:SIAM Journal on Computing
3379:Duke Mathematical Journal
3376:(1937), "Rings of sets",
3316:10.1017/S1446788700018838
2578:{\displaystyle k^{2}-k+4}
1897:{\displaystyle P\wedge Q}
1764:{\displaystyle P\wedge Q}
1692:{\displaystyle P\wedge Q}
1592:{\displaystyle P\wedge Q}
1537:{\displaystyle P\wedge Q}
1419:{\displaystyle P\wedge Q}
1320:{\displaystyle P\wedge Q}
1221:{\displaystyle P\wedge Q}
2990:{\displaystyle m(P,Q,R)}
2775:stable matching polytope
2744:Algorithmic consequences
2595:computational complexity
2466:{\displaystyle O(n^{2})}
1771:defined above, the join
3597:10.1145/3188745.3188848
2809:{\displaystyle \alpha }
2717:{\displaystyle 2^{n-1}}
2585:doctors and hospitals.
2477:Mathematical properties
1790:{\displaystyle P\vee Q}
1738:{\displaystyle P\vee Q}
1703:operations of a finite
1666:{\displaystyle P\vee Q}
1566:{\displaystyle P\vee Q}
1511:{\displaystyle P\vee Q}
1445:{\displaystyle P\vee Q}
1393:{\displaystyle P\vee Q}
1251:{\displaystyle P\vee Q}
1195:{\displaystyle P\vee Q}
680:Top and bottom elements
665:{\displaystyle P\leq R}
639:{\displaystyle Q\leq R}
613:{\displaystyle P\leq Q}
524:{\displaystyle Q\leq P}
498:{\displaystyle P\leq Q}
430:{\displaystyle P\leq P}
236:{\displaystyle P\leq Q}
3745:; Kiss, S. A. (1947),
3209:
3189:
3169:
3146:
2991:
2950:
2930:
2910:
2882:Median stable matching
2856:
2830:
2829:{\displaystyle \beta }
2810:
2794:directed acyclic graph
2718:
2685:
2643:
2623:
2579:
2540:
2520:
2500:
2467:
2431:
2404:
2372:
2352:
2332:
2284:
2264:
2240:
2220:
2200:
2180:
2122:
2042:
1965:
1945:
1925:
1898:
1872:
1852:
1831:
1811:
1791:
1765:
1739:
1693:
1667:
1633:
1613:
1593:
1567:
1538:
1512:
1486:
1466:
1446:
1420:
1394:
1361:
1341:
1321:
1292:
1272:
1252:
1228:in the following way:
1222:
1196:
1170:
1150:
1125:Gale–Shapley algorithm
1109:
1089:
1069:
1044:
1024:
1004:
984:
964:
939:
919:
894:
869:
849:
829:
809:
784:
764:
744:
724:
704:
686:Gale–Shapley algorithm
666:
640:
614:
588:
568:
548:
525:
499:
473:
453:
431:
405:
377:
357:
337:
317:
297:
277:
257:
237:
211:
121:
80:Gale–Shapley algorithm
3841:10.1287/moor.23.4.874
3210:
3190:
3170:
3147:
2992:
2951:
2931:
2911:
2857:
2831:
2811:
2719:
2686:
2644:
2624:
2580:
2541:
2521:
2501:
2468:
2432:
2430:{\displaystyle n^{2}}
2405:
2403:{\displaystyle (x,y)}
2373:
2353:
2333:
2331:{\displaystyle (x,y)}
2285:
2265:
2241:
2221:
2201:
2181:
2123:
2043:
1966:
1946:
1926:
1899:
1873:
1853:
1832:
1812:
1792:
1766:
1740:
1694:
1668:
1634:
1614:
1594:
1568:
1539:
1513:
1487:
1467:
1447:
1421:
1395:
1362:
1342:
1322:
1293:
1273:
1253:
1223:
1197:
1171:
1151:
1110:
1090:
1070:
1045:
1025:
1005:
985:
965:
940:
920:
895:
870:
850:
830:
810:
785:
765:
745:
725:
705:
667:
641:
615:
589:
569:
549:
526:
500:
474:
454:
432:
406:
378:
376:{\displaystyle \leq }
358:
338:
318:
298:
278:
258:
238:
212:
210:{\displaystyle \leq }
195:partially ordered set
122:
68:partially ordered set
3199:
3179:
3159:
3004:
2960:
2940:
2920:
2900:
2864:maximum flow problem
2840:
2820:
2800:
2730:exponential function
2695:
2653:
2633:
2613:
2550:
2530:
2510:
2490:
2441:
2414:
2382:
2362:
2342:
2310:
2292:symmetric difference
2274:
2254:
2230:
2210:
2190:
2170:
2133:distributive lattice
2058:
1978:
1955:
1935:
1915:
1882:
1862:
1842:
1821:
1801:
1775:
1749:
1723:
1705:distributive lattice
1677:
1651:
1623:
1603:
1577:
1551:
1522:
1496:
1476:
1456:
1430:
1404:
1378:
1351:
1331:
1305:
1282:
1262:
1236:
1206:
1180:
1160:
1140:
1099:
1079:
1054:
1034:
1014:
994:
974:
949:
929:
904:
879:
859:
839:
819:
794:
774:
754:
734:
714:
694:
650:
624:
598:
578:
558:
538:
509:
483:
463:
443:
415:
395:
367:
347:
327:
307:
287:
267:
247:
221:
201:
178:distributive lattice
89:
37:distributive lattice
3721:10.1145/28869.28871
2246:form a pair of the
1647:The two operations
1547:Additionally, both
391:For every matching
39:whose elements are
3707:Journal of the ACM
3205:
3185:
3165:
3142:
2987:
2946:
2926:
2906:
2852:
2826:
2806:
2767:linear programming
2714:
2681:
2639:
2619:
2575:
2536:
2516:
2496:
2463:
2427:
2400:
2368:
2348:
2328:
2280:
2260:
2236:
2216:
2196:
2176:
2118:
2038:
1961:
1941:
1921:
1894:
1868:
1848:
1827:
1807:
1787:
1761:
1735:
1689:
1663:
1643:Lattice properties
1629:
1609:
1589:
1563:
1534:
1508:
1482:
1462:
1442:
1416:
1390:
1357:
1337:
1317:
1288:
1268:
1248:
1218:
1192:
1166:
1146:
1132:Lattice operations
1105:
1085:
1068:{\displaystyle x'}
1065:
1040:
1020:
1000:
980:
963:{\displaystyle x'}
960:
935:
918:{\displaystyle x'}
915:
893:{\displaystyle x'}
890:
865:
845:
825:
808:{\displaystyle x'}
805:
780:
760:
740:
720:
700:
662:
636:
610:
584:
564:
544:
521:
495:
469:
449:
427:
401:
373:
353:
333:
313:
293:
273:
253:
233:
207:
117:
49:John Horton Conway
3743:Birkhoff, Garrett
3575:Henzinger, Monika
3374:Birkhoff, Garrett
3339:Academic Medicine
3208:{\displaystyle R}
3188:{\displaystyle Q}
3168:{\displaystyle P}
2949:{\displaystyle R}
2929:{\displaystyle Q}
2909:{\displaystyle P}
2642:{\displaystyle n}
2622:{\displaystyle n}
2539:{\displaystyle k}
2519:{\displaystyle L}
2499:{\displaystyle L}
2371:{\displaystyle y}
2351:{\displaystyle x}
2283:{\displaystyle Q}
2263:{\displaystyle P}
2248:covering relation
2239:{\displaystyle Q}
2219:{\displaystyle P}
2199:{\displaystyle Q}
2179:{\displaystyle P}
1964:{\displaystyle R}
1944:{\displaystyle Q}
1924:{\displaystyle P}
1909:distributive laws
1871:{\displaystyle Q}
1851:{\displaystyle P}
1830:{\displaystyle Q}
1810:{\displaystyle P}
1632:{\displaystyle Q}
1612:{\displaystyle P}
1485:{\displaystyle Q}
1465:{\displaystyle P}
1360:{\displaystyle Q}
1340:{\displaystyle P}
1291:{\displaystyle Q}
1271:{\displaystyle P}
1169:{\displaystyle Q}
1149:{\displaystyle P}
1108:{\displaystyle y}
1088:{\displaystyle x}
1043:{\displaystyle x}
1023:{\displaystyle y}
1003:{\displaystyle y}
983:{\displaystyle x}
938:{\displaystyle y}
868:{\displaystyle x}
848:{\displaystyle y}
828:{\displaystyle y}
783:{\displaystyle x}
763:{\displaystyle x}
743:{\displaystyle x}
723:{\displaystyle y}
703:{\displaystyle x}
587:{\displaystyle R}
567:{\displaystyle Q}
547:{\displaystyle P}
472:{\displaystyle Q}
452:{\displaystyle P}
404:{\displaystyle P}
356:{\displaystyle Q}
336:{\displaystyle P}
316:{\displaystyle P}
303:than they are in
296:{\displaystyle Q}
276:{\displaystyle P}
256:{\displaystyle Q}
66:of an underlying
3916:
3888:
3887:
3858:
3852:
3851:
3822:
3816:
3815:
3806:
3784:
3778:
3777:
3768:
3739:
3733:
3732:
3723:
3697:
3686:
3685:
3656:
3650:
3649:
3617:
3608:
3607:
3590:
3567:
3561:
3560:
3531:
3525:
3524:
3515:
3486:
3480:
3479:
3470:
3448:
3442:
3441:
3412:
3395:
3394:
3370:
3364:
3363:
3354:
3334:
3328:
3327:
3318:
3298:
3292:
3290:
3271:
3261:Knuth, Donald E.
3257:
3214:
3212:
3211:
3206:
3194:
3192:
3191:
3186:
3174:
3172:
3171:
3166:
3151:
3149:
3148:
3143:
2996:
2994:
2993:
2988:
2955:
2953:
2952:
2947:
2935:
2933:
2932:
2927:
2915:
2913:
2912:
2907:
2861:
2859:
2858:
2853:
2835:
2833:
2832:
2827:
2815:
2813:
2812:
2807:
2735:
2723:
2721:
2720:
2715:
2713:
2712:
2690:
2688:
2687:
2682:
2668:
2667:
2648:
2646:
2645:
2640:
2628:
2626:
2625:
2620:
2584:
2582:
2581:
2576:
2562:
2561:
2545:
2543:
2542:
2537:
2525:
2523:
2522:
2517:
2505:
2503:
2502:
2497:
2472:
2470:
2469:
2464:
2459:
2458:
2436:
2434:
2433:
2428:
2426:
2425:
2409:
2407:
2406:
2401:
2377:
2375:
2374:
2369:
2357:
2355:
2354:
2349:
2337:
2335:
2334:
2329:
2289:
2287:
2286:
2281:
2269:
2267:
2266:
2261:
2245:
2243:
2242:
2237:
2225:
2223:
2222:
2217:
2205:
2203:
2202:
2197:
2185:
2183:
2182:
2177:
2127:
2125:
2124:
2119:
2047:
2045:
2044:
2039:
1970:
1968:
1967:
1962:
1950:
1948:
1947:
1942:
1930:
1928:
1927:
1922:
1903:
1901:
1900:
1895:
1877:
1875:
1874:
1869:
1857:
1855:
1854:
1849:
1836:
1834:
1833:
1828:
1816:
1814:
1813:
1808:
1796:
1794:
1793:
1788:
1770:
1768:
1767:
1762:
1744:
1742:
1741:
1736:
1698:
1696:
1695:
1690:
1672:
1670:
1669:
1664:
1638:
1636:
1635:
1630:
1618:
1616:
1615:
1610:
1598:
1596:
1595:
1590:
1572:
1570:
1569:
1564:
1543:
1541:
1540:
1535:
1517:
1515:
1514:
1509:
1491:
1489:
1488:
1483:
1471:
1469:
1468:
1463:
1451:
1449:
1448:
1443:
1425:
1423:
1422:
1417:
1399:
1397:
1396:
1391:
1366:
1364:
1363:
1358:
1346:
1344:
1343:
1338:
1326:
1324:
1323:
1318:
1297:
1295:
1294:
1289:
1277:
1275:
1274:
1269:
1257:
1255:
1254:
1249:
1227:
1225:
1224:
1219:
1201:
1199:
1198:
1193:
1175:
1173:
1172:
1167:
1155:
1153:
1152:
1147:
1114:
1112:
1111:
1106:
1094:
1092:
1091:
1086:
1074:
1072:
1071:
1066:
1064:
1049:
1047:
1046:
1041:
1029:
1027:
1026:
1021:
1009:
1007:
1006:
1001:
989:
987:
986:
981:
969:
967:
966:
961:
959:
944:
942:
941:
936:
924:
922:
921:
916:
914:
899:
897:
896:
891:
889:
874:
872:
871:
866:
854:
852:
851:
846:
834:
832:
831:
826:
814:
812:
811:
806:
804:
789:
787:
786:
781:
769:
767:
766:
761:
749:
747:
746:
741:
729:
727:
726:
721:
709:
707:
706:
701:
671:
669:
668:
663:
645:
643:
642:
637:
619:
617:
616:
611:
593:
591:
590:
585:
573:
571:
570:
565:
553:
551:
550:
545:
530:
528:
527:
522:
504:
502:
501:
496:
478:
476:
475:
470:
458:
456:
455:
450:
436:
434:
433:
428:
410:
408:
407:
402:
382:
380:
379:
374:
362:
360:
359:
354:
342:
340:
339:
334:
322:
320:
319:
314:
302:
300:
299:
294:
282:
280:
279:
274:
262:
260:
259:
254:
242:
240:
239:
234:
216:
214:
213:
208:
126:
124:
123:
118:
104:
103:
41:stable matchings
29:computer science
3924:
3923:
3919:
3918:
3917:
3915:
3914:
3913:
3904:Stable matching
3894:
3893:
3892:
3891:
3859:
3855:
3823:
3819:
3785:
3781:
3740:
3736:
3698:
3689:
3657:
3653:
3639:10.1137/0216010
3618:
3611:
3571:Karlin, Anna R.
3568:
3564:
3550:10.1137/0402048
3532:
3528:
3487:
3483:
3449:
3445:
3431:10.1137/0215048
3413:
3398:
3371:
3367:
3335:
3331:
3299:
3295:
3280:
3269:
3258:
3231:
3226:
3200:
3197:
3196:
3180:
3177:
3176:
3160:
3157:
3156:
3005:
3002:
3001:
2961:
2958:
2957:
2941:
2938:
2937:
2921:
2918:
2917:
2901:
2898:
2897:
2890:
2884:
2875:Gusfield (1987)
2872:
2841:
2838:
2837:
2821:
2818:
2817:
2801:
2798:
2797:
2790:directed graphs
2786:closure problem
2763:polynomial time
2759:
2750:polynomial time
2746:
2733:
2702:
2698:
2696:
2693:
2692:
2660:
2656:
2654:
2651:
2650:
2634:
2631:
2630:
2614:
2611:
2610:
2591:
2557:
2553:
2551:
2548:
2547:
2531:
2528:
2527:
2511:
2508:
2507:
2491:
2488:
2487:
2484:
2479:
2454:
2450:
2442:
2439:
2438:
2421:
2417:
2415:
2412:
2411:
2383:
2380:
2379:
2363:
2360:
2359:
2343:
2340:
2339:
2311:
2308:
2307:
2275:
2272:
2271:
2255:
2252:
2251:
2231:
2228:
2227:
2211:
2208:
2207:
2191:
2188:
2187:
2171:
2168:
2167:
2159:, described by
2141:
2059:
2056:
2055:
1979:
1976:
1975:
1956:
1953:
1952:
1936:
1933:
1932:
1916:
1913:
1912:
1883:
1880:
1879:
1863:
1860:
1859:
1843:
1840:
1839:
1822:
1819:
1818:
1802:
1799:
1798:
1776:
1773:
1772:
1750:
1747:
1746:
1724:
1721:
1720:
1678:
1675:
1674:
1652:
1649:
1648:
1645:
1624:
1621:
1620:
1604:
1601:
1600:
1578:
1575:
1574:
1552:
1549:
1548:
1523:
1520:
1519:
1497:
1494:
1493:
1477:
1474:
1473:
1457:
1454:
1453:
1431:
1428:
1427:
1405:
1402:
1401:
1379:
1376:
1375:
1352:
1349:
1348:
1332:
1329:
1328:
1306:
1303:
1302:
1283:
1280:
1279:
1263:
1260:
1259:
1237:
1234:
1233:
1207:
1204:
1203:
1181:
1178:
1177:
1161:
1158:
1157:
1141:
1138:
1137:
1134:
1100:
1097:
1096:
1080:
1077:
1076:
1057:
1055:
1052:
1051:
1035:
1032:
1031:
1015:
1012:
1011:
995:
992:
991:
975:
972:
971:
952:
950:
947:
946:
930:
927:
926:
907:
905:
902:
901:
882:
880:
877:
876:
860:
857:
856:
840:
837:
836:
820:
817:
816:
797:
795:
792:
791:
775:
772:
771:
755:
752:
751:
735:
732:
731:
715:
712:
711:
695:
692:
691:
688:
682:
651:
648:
647:
625:
622:
621:
599:
596:
595:
579:
576:
575:
559:
556:
555:
539:
536:
535:
510:
507:
506:
484:
481:
480:
464:
461:
460:
444:
441:
440:
416:
413:
412:
396:
393:
392:
368:
365:
364:
348:
345:
344:
328:
325:
324:
308:
305:
304:
288:
285:
284:
268:
265:
264:
248:
245:
244:
222:
219:
218:
202:
199:
198:
191:
186:
137:
96:
92:
90:
87:
86:
76:polynomial time
17:
12:
11:
5:
3922:
3912:
3911:
3909:Lattice theory
3906:
3890:
3889:
3853:
3835:(4): 874–891,
3817:
3797:(2): 131–142,
3779:
3759:(1): 749–752,
3734:
3714:(3): 532–543,
3687:
3669:(3): 147–153,
3651:
3633:(1): 111–128,
3609:
3562:
3544:(4): 530–549,
3526:
3506:(2): 304–309,
3481:
3461:(3): 353–356,
3443:
3425:(3): 655–667,
3396:
3386:(3): 443–454,
3365:
3329:
3309:(3): 401–410,
3293:
3278:
3228:
3227:
3225:
3222:
3204:
3184:
3164:
3153:
3152:
3141:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3075:
3072:
3069:
3066:
3063:
3060:
3057:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3018:
3015:
3012:
3009:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2945:
2925:
2905:
2886:Main article:
2883:
2880:
2871:
2870:Minimum regret
2868:
2851:
2848:
2845:
2825:
2805:
2771:order polytope
2758:
2755:
2745:
2742:
2724:, and us also
2711:
2708:
2705:
2701:
2680:
2677:
2674:
2671:
2666:
2663:
2659:
2638:
2618:
2590:
2587:
2574:
2571:
2568:
2565:
2560:
2556:
2535:
2515:
2495:
2483:
2480:
2478:
2475:
2462:
2457:
2453:
2449:
2446:
2424:
2420:
2399:
2396:
2393:
2390:
2387:
2367:
2347:
2327:
2324:
2321:
2318:
2315:
2279:
2259:
2235:
2215:
2195:
2175:
2140:
2137:
2129:
2128:
2117:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2049:
2048:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1960:
1940:
1920:
1893:
1890:
1887:
1867:
1847:
1826:
1806:
1786:
1783:
1780:
1760:
1757:
1754:
1734:
1731:
1728:
1688:
1685:
1682:
1662:
1659:
1656:
1644:
1641:
1628:
1608:
1588:
1585:
1582:
1562:
1559:
1556:
1533:
1530:
1527:
1507:
1504:
1501:
1481:
1461:
1441:
1438:
1435:
1415:
1412:
1409:
1389:
1386:
1383:
1369:
1368:
1356:
1336:
1316:
1313:
1310:
1299:
1287:
1267:
1247:
1244:
1241:
1217:
1214:
1211:
1191:
1188:
1185:
1165:
1145:
1133:
1130:
1104:
1084:
1063:
1060:
1039:
1019:
999:
979:
958:
955:
934:
913:
910:
888:
885:
864:
844:
824:
803:
800:
779:
759:
739:
719:
699:
684:Main article:
681:
678:
674:
673:
661:
658:
655:
635:
632:
629:
609:
606:
603:
583:
563:
543:
532:
520:
517:
514:
494:
491:
488:
468:
448:
437:
426:
423:
420:
400:
372:
352:
332:
312:
292:
272:
252:
232:
229:
226:
206:
190:
187:
185:
182:
174:
173:
170:
167:
160:
159:
156:
136:
133:
116:
113:
110:
107:
102:
99:
95:
15:
9:
6:
4:
3:
2:
3921:
3910:
3907:
3905:
3902:
3901:
3899:
3886:
3882:
3878:
3874:
3870:
3866:
3865:
3857:
3850:
3846:
3842:
3838:
3834:
3830:
3829:
3821:
3814:
3810:
3805:
3800:
3796:
3792:
3791:
3783:
3776:
3772:
3767:
3762:
3758:
3754:
3753:
3748:
3744:
3738:
3731:
3727:
3722:
3717:
3713:
3709:
3708:
3703:
3702:Gusfield, Dan
3696:
3694:
3692:
3684:
3680:
3676:
3672:
3668:
3664:
3663:
3655:
3648:
3644:
3640:
3636:
3632:
3628:
3627:
3622:
3621:Gusfield, Dan
3616:
3614:
3606:
3602:
3598:
3594:
3589:
3584:
3580:
3576:
3572:
3566:
3559:
3555:
3551:
3547:
3543:
3539:
3538:
3530:
3523:
3519:
3514:
3509:
3505:
3501:
3500:
3495:
3494:Saks, Michael
3491:
3490:Gusfield, Dan
3485:
3478:
3474:
3469:
3464:
3460:
3456:
3455:
3447:
3440:
3436:
3432:
3428:
3424:
3420:
3419:
3411:
3409:
3407:
3405:
3403:
3401:
3393:
3389:
3385:
3381:
3380:
3375:
3369:
3362:
3358:
3353:
3348:
3345:(6): 477–84,
3344:
3340:
3333:
3326:
3322:
3317:
3312:
3308:
3304:
3297:
3289:
3285:
3281:
3279:0-8405-0342-3
3275:
3268:
3267:
3262:
3256:
3254:
3252:
3250:
3248:
3246:
3244:
3242:
3240:
3238:
3236:
3234:
3229:
3221:
3219:
3202:
3182:
3162:
3139:
3133:
3130:
3127:
3121:
3115:
3112:
3109:
3103:
3097:
3094:
3091:
3085:
3079:
3076:
3073:
3067:
3061:
3058:
3055:
3049:
3043:
3040:
3037:
3031:
3025:
3022:
3019:
3016:
3013:
3007:
3000:
2999:
2998:
2981:
2978:
2975:
2972:
2969:
2963:
2943:
2923:
2903:
2895:
2889:
2879:
2876:
2867:
2865:
2849:
2846:
2843:
2823:
2803:
2795:
2791:
2787:
2782:
2778:
2776:
2772:
2768:
2764:
2754:
2751:
2741:
2739:
2731:
2727:
2726:upper-bounded
2709:
2706:
2703:
2699:
2678:
2675:
2672:
2669:
2664:
2661:
2657:
2636:
2616:
2607:
2605:
2601:
2596:
2586:
2572:
2569:
2566:
2563:
2558:
2554:
2533:
2513:
2493:
2474:
2455:
2451:
2444:
2422:
2418:
2394:
2391:
2388:
2365:
2345:
2322:
2319:
2316:
2304:
2300:
2297:
2293:
2277:
2257:
2249:
2233:
2213:
2193:
2173:
2164:
2162:
2158:
2153:
2149:
2145:
2136:
2134:
2112:
2109:
2106:
2100:
2094:
2091:
2088:
2082:
2076:
2073:
2070:
2064:
2061:
2054:
2053:
2052:
2032:
2029:
2026:
2020:
2014:
2011:
2008:
2002:
1996:
1993:
1990:
1984:
1981:
1974:
1973:
1972:
1958:
1938:
1918:
1910:
1905:
1891:
1888:
1885:
1865:
1845:
1824:
1804:
1784:
1781:
1778:
1758:
1755:
1752:
1732:
1729:
1726:
1717:
1714:
1710:
1706:
1702:
1701:join and meet
1686:
1683:
1680:
1660:
1657:
1654:
1640:
1626:
1606:
1586:
1583:
1580:
1560:
1557:
1554:
1545:
1531:
1528:
1525:
1505:
1502:
1499:
1479:
1459:
1439:
1436:
1433:
1413:
1410:
1407:
1387:
1384:
1381:
1372:
1354:
1334:
1314:
1311:
1308:
1300:
1285:
1265:
1245:
1242:
1239:
1231:
1230:
1229:
1215:
1212:
1209:
1189:
1186:
1183:
1163:
1143:
1129:
1126:
1121:
1117:
1102:
1082:
1061:
1058:
1037:
1017:
997:
977:
956:
953:
932:
911:
908:
886:
883:
862:
842:
822:
801:
798:
777:
757:
737:
717:
697:
687:
677:
659:
656:
653:
633:
630:
627:
607:
604:
601:
581:
561:
541:
533:
518:
515:
512:
492:
489:
486:
466:
446:
438:
424:
421:
418:
398:
390:
389:
388:
385:
370:
350:
330:
310:
290:
270:
250:
230:
227:
224:
204:
196:
181:
179:
171:
168:
165:
164:
163:
157:
154:
153:
152:
149:
147:
143:
132:
130:
114:
111:
108:
105:
100:
97:
93:
83:
81:
77:
73:
69:
65:
61:
56:
54:
50:
46:
42:
38:
34:
30:
26:
22:
3871:(1): 34–51,
3868:
3864:Algorithmica
3862:
3856:
3832:
3826:
3820:
3794:
3788:
3782:
3756:
3750:
3737:
3711:
3705:
3666:
3660:
3654:
3630:
3624:
3578:
3565:
3541:
3535:
3529:
3503:
3502:, Series A,
3497:
3484:
3458:
3457:, Series A,
3452:
3446:
3422:
3416:
3383:
3377:
3368:
3342:
3338:
3332:
3306:
3302:
3296:
3265:
3154:
2894:median graph
2891:
2873:
2783:
2779:
2760:
2747:
2629:doctors and
2608:
2592:
2485:
2482:Universality
2305:
2301:
2165:
2156:
2142:
2130:
2050:
1906:
1718:
1646:
1546:
1373:
1370:
1135:
1122:
1118:
689:
675:
386:
263:to matching
192:
175:
161:
150:
141:
138:
84:
72:cycle graphs
57:
53:Donald Knuth
32:
18:
2604:#P-complete
2473:rotations.
2306:Every pair
2296:cycle graph
2148:finite sets
129:#P-complete
21:mathematics
3898:Categories
3588:1711.01032
3224:References
2600:antichains
2152:lower sets
1713:finite set
1374:Then both
815:both have
135:Background
64:lower sets
3131:∨
3122:∧
3113:∨
3104:∧
3095:∨
3077:∧
3068:∨
3059:∧
3050:∨
3041:∧
2850:β
2847:≤
2844:α
2836:whenever
2824:β
2804:α
2738:factorial
2707:−
2676:
2662:−
2564:−
2157:rotations
2110:∨
2101:∧
2092:∨
2074:∧
2065:∨
2030:∧
2021:∨
2012:∧
1994:∨
1985:∧
1889:∧
1782:∨
1756:∧
1730:∨
1699:form the
1684:∧
1658:∨
1584:∧
1558:∨
1529:∧
1503:∨
1437:∨
1411:∧
1385:∨
1312:∧
1243:∨
1213:∧
1187:∨
657:≤
631:≤
605:≤
531:are true.
516:≤
490:≤
422:≤
371:≤
228:≤
205:≤
184:Structure
112:
98:−
45:algebraic
25:economics
3577:(eds.),
3263:(1976),
1095:prefers
1062:′
1030:prefers
957:′
912:′
887:′
855:prefers
802:′
3885:2658099
3849:1662426
3813:0743019
3775:0021540
3730:0904192
3683:1007271
3647:0873255
3605:3826305
3558:1018538
3522:0879688
3477:0769224
3439:0850415
3361:7786367
3325:0678518
3288:0488980
3218:NP-hard
2769:to the
1709:lattice
646:, then
3883:
3847:
3811:
3773:
3728:
3681:
3645:
3603:
3556:
3520:
3475:
3437:
3359:
3323:
3286:
3276:
3195:, and
2936:, and
2728:by an
1951:, and
574:, and
142:stable
31:, the
27:, and
3583:arXiv
3270:(PDF)
2290:(the
730:that
594:, if
35:is a
3357:PMID
3274:ISBN
2358:and
2270:and
2226:and
2186:and
2051:and
1858:and
1817:and
1745:and
1673:and
1619:and
1573:and
1472:and
1400:and
1347:and
1278:and
1202:and
1156:and
1123:The
1075:and
990:and
790:and
620:and
505:and
459:and
343:and
51:and
3873:doi
3837:doi
3799:doi
3761:doi
3716:doi
3671:doi
3635:doi
3593:doi
3546:doi
3508:doi
3463:doi
3427:doi
3388:doi
3347:doi
3311:doi
2816:to
2732:of
1301:In
1232:In
1050:to
970:),
925:to
875:to
58:By
19:In
3900::
3881:MR
3879:,
3869:58
3867:,
3845:MR
3843:,
3833:23
3831:,
3809:MR
3807:,
3793:,
3771:MR
3769:,
3757:53
3755:,
3749:,
3726:MR
3724:,
3712:34
3710:,
3690:^
3679:MR
3677:,
3665:,
3643:MR
3641:,
3631:16
3629:,
3612:^
3601:MR
3599:,
3591:,
3554:MR
3552:,
3540:,
3518:MR
3516:,
3504:44
3473:MR
3471:,
3459:37
3435:MR
3433:,
3423:15
3421:,
3399:^
3382:,
3355:,
3343:70
3341:,
3321:MR
3319:,
3307:33
3305:,
3284:MR
3282:,
3232:^
3220:.
3175:,
2916:,
2866:.
2673:ln
2606:.
2163:.
2135:.
1971:,
1931:,
1639:.
1544:.
554:,
411:,
180:.
131:.
109:ln
55:.
23:,
3875::
3839::
3801::
3795:8
3763::
3718::
3673::
3667:8
3637::
3595::
3585::
3548::
3542:2
3510::
3465::
3429::
3390::
3384:3
3349::
3313::
3203:R
3183:Q
3163:P
3140:.
3137:)
3134:R
3128:Q
3125:(
3119:)
3116:R
3110:P
3107:(
3101:)
3098:Q
3092:P
3089:(
3086:=
3083:)
3080:R
3074:Q
3071:(
3065:)
3062:R
3056:P
3053:(
3047:)
3044:Q
3038:P
3035:(
3032:=
3029:)
3026:R
3023:,
3020:Q
3017:,
3014:P
3011:(
3008:m
2985:)
2982:R
2979:,
2976:Q
2973:,
2970:P
2967:(
2964:m
2944:R
2924:Q
2904:P
2734:n
2710:1
2704:n
2700:2
2679:n
2670:n
2665:1
2658:e
2637:n
2617:n
2573:4
2570:+
2567:k
2559:2
2555:k
2534:k
2514:L
2494:L
2461:)
2456:2
2452:n
2448:(
2445:O
2423:2
2419:n
2398:)
2395:y
2392:,
2389:x
2386:(
2366:y
2346:x
2326:)
2323:y
2320:,
2317:x
2314:(
2278:Q
2258:P
2234:Q
2214:P
2194:Q
2174:P
2116:)
2113:R
2107:P
2104:(
2098:)
2095:Q
2089:P
2086:(
2083:=
2080:)
2077:R
2071:Q
2068:(
2062:P
2036:)
2033:R
2027:P
2024:(
2018:)
2015:Q
2009:P
2006:(
2003:=
2000:)
1997:R
1991:Q
1988:(
1982:P
1959:R
1939:Q
1919:P
1892:Q
1886:P
1866:Q
1846:P
1825:Q
1805:P
1785:Q
1779:P
1759:Q
1753:P
1733:Q
1727:P
1687:Q
1681:P
1661:Q
1655:P
1627:Q
1607:P
1587:Q
1581:P
1561:Q
1555:P
1532:Q
1526:P
1506:Q
1500:P
1480:Q
1460:P
1440:Q
1434:P
1414:Q
1408:P
1388:Q
1382:P
1355:Q
1335:P
1315:Q
1309:P
1286:Q
1266:P
1246:Q
1240:P
1216:Q
1210:P
1190:Q
1184:P
1164:Q
1144:P
1103:y
1083:x
1059:x
1038:x
1018:y
998:y
978:x
954:x
933:y
909:x
884:x
863:x
843:y
823:y
799:x
778:x
758:x
738:x
718:y
698:x
672:.
660:R
654:P
634:R
628:Q
608:Q
602:P
582:R
562:Q
542:P
519:P
513:Q
493:Q
487:P
467:Q
447:P
425:P
419:P
399:P
351:Q
331:P
311:P
291:Q
271:P
251:Q
231:Q
225:P
115:n
106:n
101:1
94:e
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.