Решетка устойчивых паросочетаний

В математике , экономике и информатике решетка устойчивых паросочетаний представляет собой дистрибутивную решетку , элементами которой являются устойчивые паросочетания . Для данного случая устойчивой проблемы сопоставления эта решетка дает алгебраическое описание семейства всех решений проблемы. Первоначально он был описан в 1970-х годах Джоном Хортоном Конвеем и Дональдом Кнутом . ^{[ 1 ]}^{[ 2 ]}

По теореме о представлении Биркгофа эту решетку можно представить как нижние множества базового частично упорядоченного множества . Элементам этого набора можно придать конкретную структуру в виде вращений с графами циклов, описывающими изменения между соседними устойчивыми паросочетаниями в решетке. Семейство всех вращений и их частичный порядок могут быть построены за полиномиальное время , что приводит к решениям за полиномиальное время для других задач стабильного сопоставления, включая стабильное сопоставление с минимальным или максимальным весом. Алгоритм Гейла – Шепли можно использовать для построения двух специальных элементов решетки: верхнего и нижнего элементов.

Любую конечную дистрибутивную решетку можно представить как решетку устойчивых паросочетаний. Число элементов в решетке может варьироваться от среднего случая $e^{-1}n\ln n$ к худшему случаю экспоненты. Вычисление количества элементов является #P-полным .

Фон

В своей простейшей форме пример задачи устойчивого сопоставления состоит из двух наборов одинакового количества элементов, которые необходимо сопоставить друг с другом, например врачей и должностей в больницах. Каждый элемент имеет порядок предпочтений среди элементов другого типа: каждый врач имеет разные предпочтения в отношении того, в какой больнице они хотели бы работать (например, в зависимости от того, в каких городах они предпочли бы жить), и каждая больница имеет свои предпочтения. у каких врачей они хотели бы работать (например, на основании специализации или рекомендаций). соответствие Цель состоит в том, чтобы найти стабильное : ни одна пара врач и больница не предпочитают друг друга назначенному совпадению. Варианты этой проблемы используются, например, Национальной программой подбора резидентов для подбора американских студентов-медиков в больницы. ^{[ 3 ]}

В общем, может быть много разных устойчивых паросочетаний. Например, предположим, что есть три врача (A,B,C) и три больницы (X,Y,Z), которые имеют предпочтения:

А: YXZ Б: ZYX C: XZY

X: BAC Y: CBA Z: ACB

Есть три устойчивых решения этой схемы согласования:

Врачи получают свой первый выбор, а больницы — третий: AY, BZ, CX.
Все участники получают второй выбор: AX, BY, CZ.
Больницам предоставляется первый выбор, а врачам третий: AZ, BX, CY.

Решетка устойчивых паросочетаний организует этот набор решений для любого случая устойчивого паросочетания, придавая ему структуру дистрибутивной решетки . ^{[ 1 ]}

Структура

Частичный заказ на совпадения

Решетка устойчивых паросочетаний основана на следующей более слабой структуре: частично упорядоченном множестве , элементами которого являются устойчивые паросочетания. Определить операцию сравнения $\leq$ об устойчивых паросочетаниях, где $P\leq Q$ тогда и только тогда, когда все врачи предпочитают совпадение $Q$ для соответствия $P$ : либо им назначена одна и та же больница в обоих сопоставлениях, либо им назначена лучшая больница в $Q$ чем они находятся в $P$ . Если врачи не пришли к единому мнению относительно того, какое совпадение они предпочитают, то $P$ и $Q$ несравнимы: ни один из них не $\leq$ другой. Одну и ту же операцию сравнения можно определить одинаковым образом для любых двух наборов элементов, а не только для врачей и больниц. Выбор того, какой из двух наборов элементов использовать в роли врачей, произволен. Смена ролей врачей и больниц меняет порядок каждой пары элементов на обратный, но не меняет структуру частичного порядка. ^{[ 1 ]}

Тогда это упорядочение придает паросочетаниям структуру частично упорядоченного множества. Для этого он должен подчиняться следующим трем свойствам:

Для каждого совпадения $P$ , $P\leq P$
Для каждых двух разных совпадений $P$ и $Q$ , не может быть так, чтобы оба $P\leq Q$ и $Q\leq P$ верны.
На каждые три разных совпадения $P$ , $Q$ , и $R$ , если $P\leq Q$ и $Q\leq R$ , затем $P\leq R$ .

Для стабильных сопоставлений все три свойства следуют непосредственно из определения операции сравнения.

Верхние и нижние элементы

Определить наилучшее соответствие элемента $x$ стабильного соответствующего экземпляра, который будет элементом $y$ что $x$ большинство предпочитает среди всех элементов, которые могут быть сопоставлены с $x$ в стабильном паросочетании и аналогичным образом определим худшее совпадение. Тогда никакие два элемента не могут иметь одинаковое наилучшее соответствие. Ибо предположим противное, что врачи $x$ и $x'$ у обоих есть $y$ как их лучший матч, и это $y$ предпочитает $x$ к $x'$ . Затем в стабильном сопоставлении, соответствующем $x'$ к $y$ (который должен существовать по определению наилучшего соответствия $x'$ ), $x$ и $y$ будет нестабильной парой, потому что $y$ предпочитает $x$ к $x'$ и $x$ предпочитает $y$ любому другому партнеру в любом стабильном сопоставлении. Это противоречие показывает, что присвоение всем врачам наиболее подходящих вариантов дает совпадение. Это стабильное сопоставление, поскольку любая нестабильная пара также будет нестабильной для одного из паросочетаний, используемых для определения лучших совпадений. Помимо назначения всем врачам лучших совпадений, он присваивает всем больницам худшие совпадения. В частичном упорядочении паросочетаний оно больше, чем все другие стабильные паросочетания. ^{[ 1 ]}

Симметрично, присвоение всем врачам худших совпадений и присвоение всем больницам лучших совпадений дает еще одно стабильное совпадение. В частичном порядке паросочетаний он меньше, чем все остальные устойчивые паросочетания. ^{[ 1 ]}

Алгоритм Гейла-Шепли представляет собой процесс построения устойчивых сопоставлений, который можно описать следующим образом: до тех пор, пока совпадение не будет достигнуто, алгоритм выбирает произвольную больницу с незаполненной вакансией, и эта больница делает предложение о работе тому врачу, которого он предпочитает больше всего. среди тех, кому он еще не сделал предложений. Если врач безработный или у него менее предпочтительное назначение, врач принимает предложение (и отказывается от другого задания, если оно существует). Процесс всегда завершается, поскольку каждый врач и больница взаимодействуют только один раз. Когда он завершается, результатом является стабильное сопоставление, при котором каждой больнице присваивается наилучшее соответствие, а всем врачам присваиваются худшие совпадения. Алгоритм, который меняет роли врачей и больниц (при котором безработные врачи отправляют заявления о приеме на работу в следующую предпочитаемую ими больницу, а больницы принимают заявления либо тогда, когда у них есть незаполненная позиция, либо они предпочитают нового кандидата, увольняя врача, которого они ранее принятое) вместо этого создает стабильное сопоставление, которое присваивает всем врачам лучшие совпадения, а каждой больнице — худшие совпадения. ^{[ 1 ]}

Решётчатые операции

Учитывая любые два устойчивых паросочетания $P$ и $Q$ для того же входа можно сформировать еще два паросочетания $P\vee Q$ и $P\wedge Q$ следующим образом:

В

P\vee Q

, каждый врач получает лучший выбор среди двух больниц, к которым он подходит в

P

и

Q

(если они различаются), и каждая больница получает худший вариант.

В

P\wedge Q

, каждый врач получает худший выбор среди двух больниц, к которым он подходит в

P

и

Q

(если они различаются), и каждая больница получает лучший выбор.

(Одни и те же операции могут быть определены одинаковым образом для любых двух наборов элементов, а не только для врачей и больниц.) ^{[ 1 ]}

Тогда оба $P\vee Q$ и $P\wedge Q$ являются совпадениями. Например, невозможно, чтобы два врача имели один и тот же лучший выбор и были направлены в одну и ту же больницу. $P\vee Q$ , поскольку независимо от того, какой из двух врачей предпочитает больница, этот врач и больница будут образовывать нестабильную пару, в каком бы из двух случаев она ни была. $P$ и $Q$ они еще не согласованы. Потому что врачи согласованы по $P\vee Q$ , больницы также должны быть согласованы. То же рассуждение симметрично применимо и к $P\wedge Q$ . ^{[ 1 ]}

Кроме того, оба $P\vee Q$ и $P\wedge Q$ стабильны. Не может быть пары врач и больница, которая бы предпочитала друг друга своему партнеру, потому что одна и та же пара обязательно была бы нестабильной парой хотя бы для одного из них. $P$ и $Q$ . ^{[ 1 ]}

Свойства решетки

Две операции $P\vee Q$ и $P\wedge Q$ образуют операции соединения и встречи конечной дистрибутивной решетки . В этом контексте конечная решетка определяется как частично упорядоченное конечное множество , в котором существует уникальный минимальный элемент и уникальный максимальный элемент, в котором каждые два элемента имеют уникальный наименьший элемент, больший или равный им обоим (их соединение ), и каждые два элемента имеют уникальный наибольший элемент, меньший или равный им обоим (их совпадение). ^{[ 1 ]}

В случае операций $P\vee Q$ и $P\wedge Q$ определенное выше, соединение $P\vee Q$ больше или равно обоим $P$ и $Q$ потому что было определено предоставить каждому врачу предпочтительный выбор, и потому что эти предпочтения врачей определяют порядок сопоставления. Оно находится ниже любого другого соответствия, которое также выше обоих $P$ и $Q$ , потому что любое такое сопоставление должно было бы дать каждому врачу назначенное совпадение, которое, по крайней мере, столь же хорошее. Следовательно, он соответствует требованиям к операции соединения решетки. Симметрично, операция $P\wedge Q$ соответствует требованиям к проведению встречи. ^{[ 1 ]}

Поскольку они определяются с использованием поэлементного минимума или поэлементного максимума в порядке предпочтения, эти две операции подчиняются тем же законам распределения, которым подчиняются операции минимума и максимума в линейном порядке: для каждых трех различных сопоставлений $P$ , $Q$ , и $R$ ,

P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)

и

P\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)

Следовательно, решетка устойчивых паросочетаний является дистрибутивной решеткой . ^{[ 1 ]}

Представление вращением

Теорема о представлении Биркгофа утверждает, что любая конечная дистрибутивная решетка может быть представлена семейством конечных множеств с пересечением и объединением в качестве операций встречи и соединения, а также с отношением принадлежности к подмножеству в качестве операции сравнения для соответствующего частичного порядка. Более конкретно, эти множества можно рассматривать как нижние множества соответствующего частичного порядка. В общей форме теоремы Биркгофа этот частичный порядок можно рассматривать как индуцированный порядок на подмножестве элементов решетки, неприводимых к соединению элементов (элементов, которые не могут быть образованы как соединения двух других элементов). ^{[ 4 ]} Вместо этого для решетки стабильных паросочетаний элементы частичного порядка можно описать в терминах структур, называемых вращениями , описанных Ирвингом и Лезером (1986) . ^{[ 5 ]}

Предположим, что два разных устойчивых паросочетания $P$ и $Q$ сравнимы и не имеют между собой третьего устойчивого паросочетания в частичном порядке. (То есть, $P$ и $Q$ образуют пару накрывающего отношения частичного порядка устойчивых паросочетаний.) Тогда множество пар элементов, совпадающих в одном, но не в обоих из $P$ и $Q$ ( симметричная разница их наборов совпадающих пар) называется вращением. Он образует граф циклов , ребра которого чередуются между двумя паросочетаниями. Эквивалентно, ротацию можно описать как набор изменений, которые необходимо выполнить, чтобы заменить меньшее из двух совпадений на более высокое (при этом меньшее и большее определяется с использованием частичного порядка). Если два разных стабильных соответствия по отдельности являются более высоким соответствием для одного и того же вращения, то и их совпадение тоже. Отсюда следует, что для любого вращения набор устойчивых паросочетаний, которые могут быть старшими из пары, соединенной вращением, имеет уникальный наименьший элемент. Это наименьшее паросочетание является неприводимым по объединению, и это дает взаимно однозначное соответствие между вращениями и устойчивыми по объединению неприводимыми сопоставлениями. ^{[ 5 ]}

Если вращениям придан тот же частичный порядок, что и соответствующим им неприводимым в объединение стабильным паросочетаниям, то теорема Биркгофа о представлении дает взаимно однозначное соответствие между нижними наборами вращений и всеми стабильными паросочетаниями. Набор вращений, связанных с любым данным устойчивым сопоставлением, можно получить, изменив данное сопоставление на вращения вниз в частичном порядке, произвольно выбирая, какое вращение выполнять на каждом шаге, до достижения нижнего элемента, и перечисляя вращения, используемые в этой последовательности. изменений. Устойчивое паросочетание, связанное с любым нижним набором вращений, можно получить, применив вращения к нижнему элементу решетки устойчивых паросочетаний, произвольно выбирая, какое вращение применить, если можно применить более одного. ^{[ 5 ]}

Каждая пара $(x,y)$ элементов данного экземпляра стабильного соответствия принадлежит не более чем двум ротациям: одна ротация, которая при применении к меньшему из двух сопоставлений удаляет другие присвоения $x$ и $y$ и вместо этого присваивает их друг другу, а второе вращение, которое при применении к нижнему из двух совпадений удаляет пару $(x,y)$ от сопоставления и находит другие назначения для этих двух элементов. Потому что есть $n^{2}$ пары элементов, существуют $O(n^{2})$ вращения. ^{[ 5 ]}

Математические свойства

Универсальность

Помимо конечной дистрибутивной решетки, не существует других ограничений на структуру решетки устойчивых паросочетаний. Это связано с тем, что для любой конечной дистрибутивной решетки $L$ , существует экземпляр устойчивого паросочетания, решетка устойчивых паросочетаний которого изоморфна $L$ . ^{[ 6 ]} Более строго, если конечная дистрибутивная решетка имеет $k$ элементов, то это можно реализовать, используя экземпляр стабильного соответствия с не более чем $k^{2}-k+4$ врачи и больницы. ^{[ 7 ]}

Количество элементов решетки

Решетку устойчивых паросочетаний можно использовать для изучения вычислительной сложности подсчета количества устойчивых паросочетаний данного экземпляра. Из эквивалентности решеток устойчивых паросочетаний и произвольных конечных дистрибутивных решеток следует, что эта задача имеет вычислительную сложность, эквивалентную подсчету числа элементов в произвольной конечной дистрибутивной решетке или подсчету антицепей в произвольном частично упорядоченном множестве. Вычисление количества устойчивых паросочетаний является #P-полным . ^{[ 5 ]}

В равномерно случайном случае проблемы стабильного брака с $n$ врачи и $n$ больницах среднее число устойчивых паросочетаний асимптотически $e^{-1}n\ln n$ . ^{[ 8 ]} В случае стабильного брака, выбранного так, чтобы максимизировать количество различных стабильных совпадений, это число может быть не менее $2^{n-1}$ , ^{[ 5 ]} и мы также ограничены сверху экспоненциальной функцией от $n$ (значительно меньшей, чем наивная факториальная граница количества совпадений). ^{[ 9 ]}

Алгоритмические последствия

Семейство вращений и их частичное упорядочение могут быть построены за полиномиальное время на основе данного экземпляра устойчивого паросочетания и обеспечивают краткое представление семейства всех стабильных паросочетаний, которые в некоторых случаях могут быть экспоненциально больше, если они перечислены явно. Это позволяет эффективно выполнять несколько других вычислений на экземплярах стабильного соответствия. ^{[ 10 ]}

Взвешенное стабильное сопоставление и замыкание

Если каждой паре элементов в экземпляре стабильного сопоставления присвоен действительный вес, можно найти стабильное сопоставление с минимальным или максимальным весом за полиномиальное время . Одним из возможных методов для этого является применение линейного программирования к многограннику порядка частичного порядка вращений или к устойчивому совпадающему многограннику . ^{[ 11 ]} Возможен альтернативный комбинаторный алгоритм, основанный на том же частичном порядке. ^{[ 12 ]}

Из весов пар элементов можно присвоить веса каждому вращению, причем вращению, которое меняет данное устойчивое сопоставление на другое, более высокое в частичном упорядочении устойчивых сопоставлений, присваивается изменение веса, которое оно вызывает: общий вес более высокое соответствие минус общий вес более низкого соответствия. В силу соответствия между устойчивыми паросочетаниями и нижними наборами вращений общий вес любого паросочетания равен общему весу соответствующего нижнего набора плюс вес нижнего элемента решетки паросочетаний. Таким образом, проблема нахождения стабильного паросочетания минимального или максимального веса становится эквивалентной проблеме нахождения нижнего набора минимального или максимального веса в частично упорядоченном наборе полиномиального размера, частично упорядоченном наборе вращений. ^{[ 12 ]}

Эта проблема оптимального нижнего множества эквивалентна примеру проблемы замыкания , проблемы взвешенных по вершинам ориентированных графов , цель которой состоит в том, чтобы найти подмножество вершин оптимального веса без исходящих ребер. Оптимальное нижнее множество — это оптимальное замыкание ориентированного ациклического графа , вершинами которого являются элементы частичного порядка, с ребром из $\alpha$ к $\beta$ в любое время $\alpha \leq \beta$ в частичном порядке. Проблему замыкания, в свою очередь, можно решить за полиномиальное время, превратив ее в пример задачи о максимальном потоке . ^{[ 12 ]}

Я меньше всего сожалею

Гасфилд (1987) определяет сожаление участника стабильного сопоставления как расстояние назначенного ему совпадения от вершины его списка предпочтений. Он определяет сожаление о стабильном совпадении как максимальное сожаление любого участника. Тогда можно найти стабильное паросочетание с минимальным сожалением с помощью простого жадного алгоритма, который начинается с нижнего элемента решетки паросочетаний, а затем неоднократно применяет любое вращение, которое уменьшает сожаление участника с максимальным сожалением, пока это не вызовет у какого-либо другого участника чтобы иметь большее сожаление. ^{[ 10 ]}

Медианное стабильное соответствие

Элементы любой дистрибутивной решетки образуют медианный граф — структуру, в которой любые три элемента $P$ , $Q$ , и $R$ (здесь устойчивые паросочетания) имеют уникальный медианный элемент $m(P,Q,R)$ который лежит на кратчайшем пути между любыми двумя из них. Его можно определить как: ^{[ 13 ]}

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).

Для решетки стабильных совпадений эту медиану можно вместо этого взять поэлементно, назначив каждому врачу медиану в предпочтениях врача трех больниц, сопоставленных с этим врачом в $P$ , $Q$ , и $R$ и аналогичным образом, присвоив каждой больнице медианное значение трех соответствующих ей врачей. В более общем смысле, любой набор из нечетного числа элементов любой дистрибутивной решетки (или медианного графа) имеет медиану, уникальный элемент, минимизирующий сумму расстояний до данного набора. ^{[ 14 ]} Для медианы нечетного числа стабильных паросочетаний каждый участник сопоставляется с медианным элементом мультимножества его совпадений из данных паросочетаний. Для четного набора стабильных совпадений это можно устранить, выбрав задание, которое сопоставляет каждого врача с более высоким из двух медианных элементов, а каждую больницу — с меньшим из двух медианных элементов. В частности, это приводит к определению медианного паросочетания во множестве всех устойчивых паросочетаний. ^{[ 15 ]} Однако в некоторых случаях задачи устойчивого сопоставления найти эту медиану всех устойчивых паросочетаний NP-трудно . ^{[ 16 ]}

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Кнут, Дональд Э. (1976), Стабильные браки и их связь с другими комбинаторными задачами (PDF) (на французском языке), Монреаль, Квебек: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3 , МР 0488980 . См., в частности, задачу 6, стр. 87–94.
^ Хван, Дж. С. (1982), «Решетка стабильных браков и перестановок», Журнал Австралийского математического общества, серия A , 33 (3): 401–410, doi : 10.1017/S1446788700018838 , MR 0678518
^ Перансон, Э.; Рэндлетт, Р.Р. (июнь 1995 г.), «Пересмотр алгоритма сопоставления NRMP», Academic Medicine , 70 (6): 477–84, doi : 10.1097/00001888-199506000-00008 , PMID 7786367
^ Биркгоф, Гаррет (1937), «Кольца множеств», Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215/S0012-7094-37-00334-X
^ Jump up to: ^а ^б ^с ^д ^и ^ж Ирвинг, Роберт В.; Лезер, Пол (1986), «Сложность подсчета стабильных браков», SIAM Journal on Computing , 15 (3): 655–667, doi : 10.1137/0215048 , MR 0850415
^ Блер, Чарльз (1984), «Каждая конечная дистрибутивная решетка представляет собой набор устойчивых паросочетаний», Журнал комбинаторной теории , серия A, 37 (3): 353–356, doi : 10.1016/0097-3165(84)90056-6 , МР 0769224
^ Гасфилд, Дэн ; Ирвинг, Роберт; Кожа, Пол; Сакс, Майкл (1987), «Каждая конечная дистрибутивная решетка представляет собой набор стабильных паросочетаний для небольшого экземпляра стабильного брака», Журнал комбинаторной теории , серия A, 44 (2): 304–309, doi : 10.1016/0097-3165 (87)90037-9 , МР 0879688
^ Питтель, Борис (1989), «Среднее количество устойчивых паросочетаний», SIAM Journal on Discrete Mathematics , 2 (4): 530–549, doi : 10.1137/0402048 , MR 1018538
^ Карлин, Анна Р .; Гаран, Шаян Овейс; Вебер, Робби (2018), «Просто экспоненциальная верхняя граница максимального количества устойчивых паросочетаний», в Диакониколасе, Илиасе; Кемпе, Дэвид; Хенцингер, Моника (ред.), Труды 50-го симпозиума по теории вычислений (STOC 2018) , Ассоциация вычислительной техники, стр. 920–925, arXiv : 1711.01032 , doi : 10.1145/3188745.3188848 , MR 3826305
^ Jump up to: ^а ^б Гасфилд, Дэн (1987), «Три быстрых алгоритма для четырех проблем в стабильном браке», SIAM Journal on Computing , 16 (1): 111–128, doi : 10.1137/0216010 , MR 0873255
^ Ванде Вейт, Джон Х. (1989), «Линейное программирование приносит семейное счастье», Operations Research Letters , 8 (3): 147–153, doi : 10.1016/0167-6377(89)90041-2 , MR 1007271
^ Jump up to: ^а ^б ^с Ирвинг, Роберт В.; Кожа, Пол; Гасфилд, Дэн (1987), «Эффективный алгоритм для «оптимального» стабильного брака», Journal of the ACM , 34 (3): 532–543, doi : 10.1145/28869.28871 , MR 0904192
^ Биркгоф, Гарретт ; Кисс, С.А. (1947), «Трнарная операция в распределительных решетках» , Бюллетень Американского математического общества , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR 0021540
^ Бандельт, Ханс-Юрген; Бартелеми, Жан-Пьер (1984), «Медианы в медианных графиках», Discrete Applied Mathematics , 8 (2): 131–142, doi : 10.1016/0166-218X(84)90096-9 , MR 0743019
^ Тео, Чунг-Пио; Сетураман, Джей (1998), «Геометрия дробно-устойчивых паросочетаний и ее приложения», Mathematics of Operations Research , 23 (4): 874–891, doi : 10.1287/moor.23.4.874 , MR 1662426
^ Ченг, Кристин Т. (2010), «Понимание обобщенных медианных стабильных паросочетаний», Algorithmica , 58 (1): 34–51, doi : 10.1007/s00453-009-9307-2 , MR 2658099

[knuth-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Кнут, Дональд Э. (1976), Стабильные браки и их связь с другими комбинаторными задачами (PDF) (на французском языке), Монреаль, Квебек: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3 , МР 0488980 . См., в частности, задачу 6, стр. 87–94.

[hwang-2] Хван, Дж. С. (1982), «Решетка стабильных браков и перестановок», Журнал Австралийского математического общества, серия A , 33 (3): 401–410, doi : 10.1017/S1446788700018838 , MR 0678518

[pram-3] Перансон, Э.; Рэндлетт, Р.Р. (июнь 1995 г.), «Пересмотр алгоритма сопоставления NRMP», Academic Medicine , 70 (6): 477–84, doi : 10.1097/00001888-199506000-00008 , PMID 7786367

[birkhoff-4] Биркгоф, Гаррет (1937), «Кольца множеств», Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215/S0012-7094-37-00334-X

[il-5] Jump up to: ^а ^б ^с ^д ^и ^ж Ирвинг, Роберт В.; Лезер, Пол (1986), «Сложность подсчета стабильных браков», SIAM Journal on Computing , 15 (3): 655–667, doi : 10.1137/0215048 , MR 0850415

[blair-6] Блер, Чарльз (1984), «Каждая конечная дистрибутивная решетка представляет собой набор устойчивых паросочетаний», Журнал комбинаторной теории , серия A, 37 (3): 353–356, doi : 10.1016/0097-3165(84)90056-6 , МР 0769224

[gils-7] Гасфилд, Дэн ; Ирвинг, Роберт; Кожа, Пол; Сакс, Майкл (1987), «Каждая конечная дистрибутивная решетка представляет собой набор стабильных паросочетаний для небольшого экземпляра стабильного брака», Журнал комбинаторной теории , серия A, 44 (2): 304–309, doi : 10.1016/0097-3165 (87)90037-9 , МР 0879688

[pittel-8] Питтель, Борис (1989), «Среднее количество устойчивых паросочетаний», SIAM Journal on Discrete Mathematics , 2 (4): 530–549, doi : 10.1137/0402048 , MR 1018538

[kgw-9] Карлин, Анна Р .; Гаран, Шаян Овейс; Вебер, Робби (2018), «Просто экспоненциальная верхняя граница максимального количества устойчивых паросочетаний», в Диакониколасе, Илиасе; Кемпе, Дэвид; Хенцингер, Моника (ред.), Труды 50-го симпозиума по теории вычислений (STOC 2018) , Ассоциация вычислительной техники, стр. 920–925, arXiv : 1711.01032 , doi : 10.1145/3188745.3188848 , MR 3826305

[gusfield-10] Jump up to: ^а ^б Гасфилд, Дэн (1987), «Три быстрых алгоритма для четырех проблем в стабильном браке», SIAM Journal on Computing , 16 (1): 111–128, doi : 10.1137/0216010 , MR 0873255

[vv-11] Ванде Вейт, Джон Х. (1989), «Линейное программирование приносит семейное счастье», Operations Research Letters , 8 (3): 147–153, doi : 10.1016/0167-6377(89)90041-2 , MR 1007271

[ilg-12] Jump up to: ^а ^б ^с Ирвинг, Роберт В.; Кожа, Пол; Гасфилд, Дэн (1987), «Эффективный алгоритм для «оптимального» стабильного брака», Journal of the ACM , 34 (3): 532–543, doi : 10.1145/28869.28871 , MR 0904192

[bk-13] Биркгоф, Гарретт ; Кисс, С.А. (1947), «Трнарная операция в распределительных решетках» , Бюллетень Американского математического общества , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR 0021540

[bb-14] Бандельт, Ханс-Юрген; Бартелеми, Жан-Пьер (1984), «Медианы в медианных графиках», Discrete Applied Mathematics , 8 (2): 131–142, doi : 10.1016/0166-218X(84)90096-9 , MR 0743019

[ts-15] Тео, Чунг-Пио; Сетураман, Джей (1998), «Геометрия дробно-устойчивых паросочетаний и ее приложения», Mathematics of Operations Research , 23 (4): 874–891, doi : 10.1287/moor.23.4.874 , MR 1662426

[cheng-16] Ченг, Кристин Т. (2010), «Понимание обобщенных медианных стабильных паросочетаний», Algorithmica , 58 (1): 34–51, doi : 10.1007/s00453-009-9307-2 , MR 2658099

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]