В математике , экономике и информатике , то решетка стабильного паросочетания является дистрибутивной решеткой , элементы которой является стабильным паросочетанием . Для данного случая стабильной задачи согласования эта решетка обеспечивает алгебраическое описание семейства всех решений проблемы. Первоначально он был описан в 1970-х Джоном Хортоном Конвеем и Дональдом Кнутом . [1] [2]
По теореме Биркгофа о представлении эта решетка может быть представлена как нижние множества нижележащего частично упорядоченного множества , а элементам этого множества может быть придана конкретная структура в виде вращений, цикловых графов, описывающих изменения между соседними стабильными сопоставлениями в решетке. Семейство всех вращений и их частичный порядок могут быть построены за полиномиальное время , что приводит к полиномиальному времени для других задач по устойчивому согласованию, включая стабильное согласование с минимальным или максимальным весом. Алгоритм Гейла-Шепли может быть использован для построения две специальных элементов, решеток ее верхних и нижний элемента.
Каждую конечную дистрибутивную решетку можно представить как решетку стабильных паросочетаний. Количество элементов в решетке может варьироваться от среднего случаяв худшем случае экспоненциального. Вычисление количества элементов # Р-полной .
Задний план
В своей простейшей форме пример задачи стабильного согласования состоит из двух наборов с одинаковым количеством элементов, которые должны быть согласованы друг с другом, например, врачей и должности в больницах. Каждый элемент имеет порядок предпочтений по отношению к элементам другого типа: каждый врач имеет разные предпочтения относительно того, в какой больнице они хотели бы работать (например, в зависимости от того, в каком городе они предпочли бы жить), и у каждой больницы есть предпочтения. у каких врачей они хотели бы работать (например, по специализации или рекомендациям). Цель состоит в том, чтобы найти стабильное соответствие : ни одна пара врача и больницы не предпочла бы друг друга назначенному им совпадению. Варианты этой задачи используются, например, в Национальной программе подбора жильцов для сопоставления американских студентов-медиков с больницами. [3]
В общем, может быть много разных стабильных соответствий. Например, предположим, что есть три врача (A, B, C) и три больницы (X, Y, Z), которые имеют следующие предпочтения:
- А: YXZ B: ZYX C: XZY
- X: BAC Y: CBA Z: ACB
Есть три стабильных решения этого согласования:
- Доктора получают свой первый выбор, а больницы - третий: AY, BZ, CX.
- Всем участникам предоставляется второй выбор: AX, BY, CZ.
- Больницы получают первый выбор, а врачи - третий: AZ, BX, CY.
Решетка стабильных согласований организует этот набор решений для любого случая стабильного согласования, придавая ему структуру распределительной решетки . [1]
Состав
Частичный заказ на совпадения
Решетка стабильных паросочетаний основана на следующей более слабой структуре - частично упорядоченном множестве , элементами которого являются стабильные паросочетания. Определите операцию сравнения на стабильных сопоставлениях, где тогда и только тогда, когда все врачи предпочитают сопоставление к соответствию : либо им назначена одна и та же больница в обоих матчах, либо им назначают лучшую больницу в чем они в . Если врачи не согласны с тем, какое соответствие они предпочитают, тогда а также несравнимы: ни один не другой. Одна и та же операция сравнения может быть определена одинаково для любых двух наборов элементов, а не только для врачей и больниц. Выбор того, какой из двух наборов элементов использовать в роли врачей, является произвольным. Обмен ролями врачей и больниц меняет порядок каждой пары элементов на противоположный, но не меняет структуру частичного порядка. [1]
Тогда этот порядок придает сопоставлениям структуру частично упорядоченного множества. Для этого он должен подчиняться следующим трем свойствам:
- Для каждого совпадения ,
- Для каждых двух разных совпадений а также , не может быть случая, чтобы оба а также верны.
- Для каждых трех разных совпадений , , а также , если а также , тогда .
Для стабильных сопоставлений все три свойства следуют непосредственно из определения операции сравнения.
Верхний и нижний элементы
Определите наилучшее соответствие элемента стабильного совпадающего экземпляра быть элементом что большинство предпочитает среди всех элементов, которые могут быть сопоставлены с в стабильном сопоставлении и аналогичным образом определите наихудшее совпадение. Тогда никакие два элемента не могут иметь одинаковое наилучшее совпадение. Ибо предположим противное, что врачи а также как есть как их лучший матч, и это предпочитает к . Затем в стабильном сопоставлении, которое соответствует к (который должен существовать по определению наилучшего соответствия ), а также будет нестабильной парой, потому что предпочитает к а также предпочитает любому другому партнеру в любом стабильном матче. Это противоречие показывает, что присвоение всем докторам их лучших совпадений дает совпадение. Это стабильное сопоставление, потому что любая нестабильная пара также будет нестабильной для одного из сопоставлений, используемых для определения наилучшего сопоставления. Кроме того, что всем врачам назначаются их лучшие матчи, все больницы назначаются на их худшие матчи. При частичном упорядочивании сопоставлений он больше, чем все другие стабильные сопоставления. [1]
Симметрично, распределение всех врачей с их худшими совпадениями и назначение всех больниц с их лучшими совпадениями дает еще одно стабильное совпадение. В частичном порядке сопоставлений он меньше, чем все другие стабильные сопоставления. [1]
Алгоритм Гейла-Шепли дает способ построения стабильных паросочетания, которое можно описать следующим образом : до соответствия не будет достигнуто, то алгоритм выбирает произвольную больницу с незаполненной позиции, и что больница делает предложение о работе к врачу большинство предпочитает среди тех, кому он еще не делал предложения. Если врач не работает или у него менее предпочтительное назначение, он принимает предложение (и увольняется с другого назначения, если оно существует). Процесс всегда завершается, потому что каждый врач и больница взаимодействуют только один раз. Когда он завершается, результатом является стабильное сопоставление, при котором каждой больнице присваивается наилучшее соответствие, а всем врачам присваиваются наихудшие совпадения. Алгоритм, который меняет роли врачей и больниц (в котором безработные врачи отправляют заявки на работу по своему следующему предпочтению среди больниц, а больницы принимают заявки либо когда у них есть незаполненная должность, либо они предпочитают нового кандидата, увольняя врача, которого они ранее был принят) вместо этого производит стабильное сопоставление, которое назначает всех врачей их лучшим совпадениям и каждой больнице - худшим совпадениям. [1]
Решетчатые операции
Учитывая любые два стабильных соответствия а также для того же входа можно сформировать еще два сопоставления а также следующим образом:
- В , каждый врач получает лучший выбор среди двух больниц, в которых он находится. а также (если они отличаются), и каждая больница получает свой худший выбор.
- В , каждый врач получает худший выбор среди двух больниц, в которые они попадают. а также (если они отличаются), и каждая больница получает свой лучший выбор.
(Одни и те же операции могут быть определены одинаково для любых двух наборов элементов, а не только для врачей и больниц.) [1]
Тогда оба а также совпадают. Например, невозможно, чтобы у двух врачей был один и тот же лучший выбор и они работали в одной и той же больнице в, поскольку независимо от того, какого из двух врачей предпочитает больница, этот врач и больница составят нестабильную пару в зависимости от того, а также они еще не сопоставлены. Поскольку врачи сопоставлены в , больницы также должны быть сопоставлены. Те же рассуждения симметрично применимы к. [1]
Кроме того, оба а также стабильны. Не может быть пары, состоящей из врача и больницы, которые предпочли бы друг друга своему матчу, потому что одна и та же пара обязательно также будет нестабильной парой по крайней мере для одного из них. а также . [1]
Свойства решетки
Две операции а также образуют операции соединения и встречи конечной дистрибутивной решетки . В этом контексте конечная решетка определяется как частично упорядоченное конечное множество, в котором есть уникальный минимальный элемент и уникальный максимальный элемент, в котором каждые два элемента имеют уникальный наименьший элемент, больший или равный им обоим (их соединение ), и каждые два элемента имеют единственный наибольший элемент, меньший или равный им обоим (их встреча). [1]
В случае операций а также определено выше, соединение больше или равно обоим а также потому что это было определено, чтобы дать каждому врачу их предпочтительный выбор, и потому что эти предпочтения врачей определяют порядок сопоставления. Это ниже любого другого соответствия, которое также выше обоих а также , потому что любое такое сопоставление должно дать каждому врачу назначенное сопоставление, которое, по крайней мере, не менее хорошее. Следовательно, он соответствует требованиям для операции соединения решетки. Симметрично операциясоответствует требованиям для выполнения операции. [1]
Поскольку они определены с использованием поэлементного минимума или поэлементного максимума в порядке предпочтения, эти две операции подчиняются одним и тем же законам распределения, которым подчиняются операции минимума и максимума в линейном порядке: для каждых трех различных сопоставлений, , а также ,
а также
Следовательно, решетка стабильных паросочетаний является дистрибутивной решеткой . [1]
Представление вращениями
Теорема Биркгофа о представлении утверждает, что любая конечная дистрибутивная решетка может быть представлена семейством конечных множеств с пересечением и объединением в качестве операций пересечения и соединения и с отношением быть подмножеством в качестве операции сравнения для соответствующего частичного порядка. Более конкретно, эти наборы можно рассматривать как нижние наборы ассоциированного частичного порядка. В общей форме теоремы Биркгофа этот частичный порядок может быть взят как индуцированный порядок на подмножестве элементов решетки, неприводимых соединением элементов (элементов, которые не могут быть образованы как соединения двух других элементов). [4] Для решетки стабильных согласований элементы частичного порядка вместо этого могут быть описаны в терминах структур, называемых вращениями , описанных Irving & Leather (1986) . [5]
Предположим, что два разных стабильных сопоставления а также сопоставимы и не имеют третьего устойчивого соответствия между собой в частичном порядке. (Это, а также образуют пару покрывающих отношений частичного порядка стабильных паросочетаний.) Тогда множество пар элементов, которые совпадают в одном, но не в обоих, а также ( симметричная разность их наборов согласованных пар) называется вращением. Он образует граф циклов, чьи ребра чередуются между двумя сопоставлениями. Эквивалентно вращение можно описать как набор изменений, которые необходимо будет выполнить, чтобы изменить более низкое из двух сопоставлений на более высокое (при этом более низкие и высокие значения определяются с использованием частичного порядка). Если два разных стабильных соответствия по отдельности являются более высоким соответствием для одного и того же вращения, то их соответствие также является их совпадением. Отсюда следует, что для любого вращения набор стабильных соответствий, которые могут быть высшими из пары, соединенной вращением, имеет уникальный наименьший элемент. Это наименьшее сопоставление является неприводимым по объединению, и это дает взаимно однозначное соответствие между поворотами и устойчивыми сопоставлениями, не приводящими к объединению. [5]
Если вращениям задается такой же частичный порядок, как и их соответствующие неразложимые по соединению стабильные сопоставления, то теорема Биркгофа о представлении дает взаимно однозначное соответствие между нижними наборами вращений и всеми стабильными сопоставлениями. Набор поворотов, связанных с любым заданным стабильным соответствием, может быть получен путем изменения данного совпадения вращениями вниз в частичном порядке, произвольным выбором вращения для каждого шага до достижения нижнего элемента и перечислением поворотов, используемых в этой последовательности. изменений. Устойчивое согласование, связанное с любым нижним набором поворотов, может быть получено путем применения поворотов к нижнему элементу решетки стабильных сопоставлений, произвольно выбирая, какое вращение применять, когда может применяться более одного. [5]
Каждая пара элементов данного стабильного экземпляра сопоставления принадлежит не более чем двум поворотам: одно вращение, применяемое к более низкому из двух сопоставлений, удаляет другие назначения для а также и вместо этого назначает их друг другу, а второе вращение, применяемое к более низкому из двух сопоставлений, удаляет пару из сопоставления и находит другие назначения для этих двух элементов. Потому что есть пары элементов, есть вращения. [5]
Математические свойства
Универсальность
Помимо конечной дистрибутивной решетки, нет никаких других ограничений на решеточную структуру стабильных паросочетаний. Это потому, что для любой конечной дистрибутивной решетки, существует устойчивый экземпляр паросочетания, решетка стабильных паросочетаний которого изоморфна . [6] Более того, если конечная дистрибутивная решетка имеет элементов, то это может быть реализовано с использованием стабильного совпадающего экземпляра с не более чем врачи и больницы. [7]
Количество элементов решетки
Решетка стабильных сопоставлений может использоваться для изучения вычислительной сложности подсчета числа стабильных сопоставлений данного экземпляра. Из эквивалентности решеток стабильных паросочетаний и произвольных конечных дистрибутивных решеток следует, что эта задача имеет эквивалентную вычислительную сложность подсчету числа элементов в произвольной конечной дистрибутивной решетке или подсчету антицепей в произвольном частично упорядоченном множестве. Вычисление числа устойчивых паросочетаний является # Р-полной . [5]
В равномерно-случайном примере стабильной проблемы брака с врачи и больниц, среднее количество стабильных сопоставлений асимптотически . [8] В случае стабильного брака, выбранного для максимального количества различных стабильных совпадений, это число может быть не менее, [5] , а также , ограничена сверху посредством экспоненциальной функции от п (значительно меньше , чем наивным факториала граница числа паросочетаний). [9]
Алгоритмические последствия
Семейство поворотов и их частичное упорядочение могут быть построены за полиномиальное время из данного экземпляра стабильного сопоставления и обеспечивают краткое представление семейства всех стабильных сопоставлений, которое для некоторых случаев может быть экспоненциально больше, если указано явно. Это позволяет эффективно выполнять несколько других вычислений на стабильных совпадающих экземплярах. [10]
Взвешенное стабильное соответствие и закрытие
Если каждой паре элементов в экземпляре устойчивого сопоставления присваивается действительный вес, можно найти стабильное сопоставление с минимальным или максимальным весом за полиномиальное время . Один из возможных методов для этого - применить линейное программирование к многограннику порядка частичного порядка вращений или к устойчивому согласованному многограннику . [11] Возможен альтернативный комбинаторный алгоритм, основанный на том же частичном порядке. [12]
Из весов пар элементов можно присвоить веса каждому вращению, где вращению, которое изменяет данное стабильное соответствие на другое более высокое в частичном порядке стабильных соответствий, назначается изменение веса, которое оно вызывает: общий вес более высокое соответствие минус общий вес более низкого соответствия. Благодаря соответствию между стабильными сопоставлениями и нижними наборами поворотов общий вес любого сопоставления равен общему весу его соответствующего нижнего набора плюс вес нижнего элемента решетки сопоставлений. Таким образом, проблема поиска стабильного соответствия минимального или максимального веса становится эквивалентной проблеме поиска нижнего набора минимального или максимального веса в частично упорядоченном наборе полиномиального размера, частично упорядоченном множестве поворотов. [12]
Эта задача оптимального нижнего множества эквивалентна случаю проблемы замыкания , проблеме ориентированных графов, взвешенных по вершинам, цель которой состоит в том, чтобы найти подмножество вершин оптимального веса без исходящих ребер. Оптимальное нижнее множество - это оптимальное замыкание ориентированного ациклического графа , вершинами которого являются элементы частичного порядка, с ребром из к в любое время в частичном порядке. Проблема замыкания, в свою очередь, может быть решена за полиномиальное время, преобразовав ее в пример задачи о максимальном потоке . [12]
Минимум сожалений
Гусфилд (1987) определяет сожаление участника стабильного сопоставления как расстояние от назначенного ему совпадения до вершины его списка предпочтений. Он определяет сожаление о стабильном совпадении как максимальное сожаление для любого участника. Затем можно найти стабильное сопоставление с минимальным сожалением с помощью простого жадного алгоритма, который начинается с нижнего элемента решетки сопоставлений, а затем многократно применяет любое вращение, которое уменьшает сожаление участника с максимальным сожалением, пока это не вызовет у другого участника иметь большее сожаление. [10]
Среднее стабильное соответствие
Элементы любой дистрибутивной решетки образуют медианный граф , структуру, в которой любые три элемента, , а также (здесь стабильные сопоставления) имеют уникальный медианный элемент который лежит на кратчайшем пути между любыми двумя из них. Его можно определить как: [13]
Для решетки стабильных сопоставлений эту медиану можно взять поэлементно, назначив каждому врачу медианное значение в предпочтениях врачей трех больниц, сопоставленных с этим врачом в , , а также и аналогичным образом присвоив каждой больнице медианное значение из трех соответствующих ей врачей. В более общем смысле, любой набор из нечетного числа элементов любой распределительной решетки (или медианного графа) имеет медиану, уникальный элемент, минимизирующий его сумму расстояний до данного набора. [14] Для медианы нечетного числа стабильных сопоставлений каждый участник сопоставляется со средним элементом мультимножества их совпадений из данных сопоставлений. Для равномерного набора стабильных сопоставлений это можно устранить, выбрав назначение, которое сопоставляет каждого врача с высшим из двух средних элементов, а каждой больнице - с более низким из двух средних элементов. В частности, это приводит к определению медианного сопоставления во множестве всех стабильных сопоставлений. [15] Однако для некоторых примеров проблемы стабильного сопоставления найти эту медиану всех стабильных сопоставлений NP-сложно . [16]
Рекомендации
- ^ a b c d e f g h i j k l Кнут, Дональд Э. (1976), Mariages stables et leurs Relations avec d'autres problèmes combinatoires (PDF) (на французском языке), Монреаль, Квебек: Les Presses de l ' Университет Монреаля, ISBN 0-8405-0342-3, Руководство по ремонту 0488980. См., В частности, проблему 6, стр. 87–94.
- ^ Хван, JS (1982), "Решетка стабильных браков и перестановок", журнал Австралийского математического общества, Series A , 33 (3): 401-410, DOI : 10,1017 / S1446788700018838 , МР 0678518
- ^ Перансон, Э .; Randlett, RR (июнь 1995), "Алгоритм NRMP соответствия вновь", Academic Medicine , 70 (6): 477-84, DOI : 10,1097 / 00001888-199506000-00008 , PMID 7786367
- ^ Биркгофу, Гаррет (1937), "Кольцо множеств", Герцога математического журнал , 3 (3): 443-454, DOI : 10,1215 / S0012-7094-37-00334-X ,
- ^ а б в г д е Ирвинг, Роберт В .; Кожа, Пол (1986), "Сложность подсчета стабильных браков", SIAM журнал по вычислениям , 15 (3): 655-667, DOI : 10,1137 / 0215048 , МР 0850415
- ^ Блэр, Чарльз (1984), "Всякая конечная дистрибутивная решетка представляет собой набор стабильных паросочетания", Журнал комбинаторной теории , Серия А, 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
- ^ Pittel, Б. (1989), "Среднее число стабильных паросочетаний", SIAM журнал по дискретной математике , 2 (4): 530-549, DOI : 10,1137 / 0402048 , МР 1018538
- ^ Карлин, Анна Р .; Гаран, Шаян Овейс; Вебер, Робби (2018), «Просто экспоненциальная верхняя граница максимального числа стабильных сопоставлений», в Диакониколасе, Илиас; Кемпе, Дэвид; Хенцингер, Моника (ред.), Труды 50-го симпозиума по теории вычислений (STOC 2018) , Ассоциация вычислительной техники, стр. 920–925, arXiv : 1711.01032 , doi : 10.1145 / 3188745.3188848 , MR 3826305
- ^ а б Gusfield, Дан (1987), "Три быстрых алгоритмов для четырех проблем в стабильном браке", SIAM журнал по вычислениям , 16 (1): 111-128, DOI : 10,1137 / 0216010 , MR 0873255
- ^ Ванда Va, Джон Х. (1989), "Линейное программирование приносит семейное счастье", исследование операций письма , 8 (3): 147-153, DOI : 10.1016 / 0167-6377 (89) 90041-2 , MR 1007271
- ^ а б в Ирвинг, Роберт В .; Кожа, Пол; Gusfield, Dan (1987), "Эффективный алгоритм для "оптимального" стабильного брака", Журнал ACM , 34 (3): 532-543, DOI : 10,1145 / 28869,28871 , МР 0904192
- ^ Биркгоф, Гарретт ; Поцелуй, SA (1947), "Тройная операция в дистрибутивных решеток" , Бюллетень Американского математического общества , 53 (1): 749-752, DOI : 10,1090 / S0002-9904-1947-08864-9 , MR 0021540
- ^ Бандельт, Ханс-Юрген; Бартелей, Жан-Пьер (1984), "Медиана в срединных графах", Дискретная прикладная математика , 8 (2): 131-142, DOI : 10.1016 / 0166-218X (84) 90096-9 , МР 0743019
- ^ Тео, Чунг-Пиау; Sethuraman, Джей (1998), "Геометрия дробно стабильных паросочетаний и ее приложения", математики исследования операций , 23 (4): 874-891, DOI : 10.1287 / moor.23.4.874 , МР 1662426
- ^ Ченг, Кристин Т. (2010), "Понимание обобщенных срединные стабильных паросочетаний", Algorithmica , 58 (1): 34-51, DOI : 10.1007 / s00453-009-9307-2 , МР 2658099