Стабильный совпадающий многогранник
В математике , экономике и информатике устойчивый многогранник соответствия или стабильный многогранник брака представляет собой выпуклый многогранник, полученный из решений экземпляра проблемы устойчивого соответствия . [1] [2]
Описание
[ редактировать ]Многогранник устойчивого паросочетания представляет собой выпуклую оболочку индикаторных векторов устойчивых паросочетаний данной задачи. Он имеет размерность для каждой пары элементов, которые могут быть сопоставлены, и вершину для каждого стабильного сопоставления. Для каждой вершины декартовы координаты равны единице для пар, которые совпадают при соответствующем сопоставлении, и нулю для пар, которые не совпадают. [1]
Устойчивый совпадающий многогранник имеет полиномиальное число граней . К ним относятся традиционные неравенства, описывающие сопоставления без требования устойчивости (каждая координата должна находиться в диапазоне от 0 до 1, и для каждого сопоставляемого элемента сумма координат для пар, включающих этот элемент, должна быть ровно единица), а также неравенства, ограничивающие результирующее сопоставление должно быть стабильным (для каждого потенциально совпадающего элемента пары сумма координат для совпадений, которые, по крайней мере, столь же хороши для одного из двух элементов, должна быть не менее единицы). Точки, удовлетворяющие всем этим ограничениям, можно рассматривать как дробные решения релаксации линейного программирования задачи устойчивого сопоставления.
Целостность
[ редактировать ]Это теорема Ванде Вейта (1989) , согласно которой многогранник, описываемый перечисленными выше ограничениями фасетов, имеет только вершины, описанные выше. В частности, это целый многогранник . Это можно рассматривать как аналог теоремы Гаррета Биркгофа о том, что аналогичный многогранник, многогранник Биркгофа, описывающий множество всех дробных паросочетаний между двумя множествами, является целым. [3]
Эквивалентный способ формулировки той же теоремы состоит в том, что каждое дробное паросочетание можно выразить как выпуклую комбинацию целочисленных паросочетаний. Тео и Сетураман (1998) доказывают это, строя распределение вероятностей для целочисленных паросочетаний, математическое ожидание которого можно установить равным любому заданному дробному паросочетанию. Для этого они выполняют следующие шаги:
- Рассмотрим для каждого элемента на одной стороне задачи устойчивого сопоставления (скажем, врачей в задаче сопоставления врачей и больниц) дробные значения, присвоенные парам с элементами на другой стороне (больницы), и отсортируйте эти значения по убыванию. заказывайте по предпочтениям этого врача.
- Разделите единичный интервал на подинтервалы длиной, равной этим дробным значениям, в отсортированном порядке. Выбор случайного числа в единичном интервале даст случайное совпадение для выбранного врача с вероятностью, равной дробному весу этого совпадения.
- Симметрично рассмотрим каждый элемент на другой стороне стабильного соответствия (больницы), отсортируем дробные значения для пар, включающих этот элемент, в порядке возрастания предпочтений и построим разбиение единичного интервала, подинтервалы которого имеют эти дробные значения в отсортированный порядок.
- Можно доказать, что для каждой совпавшей пары подинтервалы, связанные с этой парой, одинаковы как в разделе для врача, так и в разделе для больницы в этой паре. Таким образом, выбор одного случайного числа в единичном интервале и использование этого выбора для одновременного выбора больницы для каждого врача и врача для каждой больницы дает совпадение. Более того, можно показать, что это сопоставление устойчиво.
В результате случайно выбранного устойчивого сопоставления выбирается любая конкретная совпавшая пара с вероятностью, равной дробному значению координаты этой пары.Таким образом, построенное таким образом распределение вероятностей по устойчивым паросочетаниям дает представление данного дробного паросочетания как выпуклой комбинации целочисленных устойчивых паросочетаний. [4]
Решетка дробных паросочетаний
[ редактировать ]Семейство всех стабильных паросочетаний образует распределительную решетку , решетку стабильных паросочетаний , в которой объединение двух паросочетаний дает всем врачам предпочтение среди назначенных им больниц в двух сопоставлениях, а совпадение дает предпочтение всем больницам. [5] То же самое относится и к семейству всех дробных устойчивых паросочетаний, точкам устойчивого многогранника паросочетания. [3]
В стабильном многограннике соответствия можно определить, что одно сопоставление доминирует над другим, если для каждого врача и больницы общее дробное значение, присвоенное совпадениям для этого врача, которые по крайней мере так же хороши (для врача), как и эта больница, не менее большой в первом сопоставлении, как и во втором.Это определяет частичный порядок дробных паросочетаний. Этот частичный порядок имеет уникальный наибольший элемент — целочисленное стабильное совпадение, найденное с помощью версии алгоритма Гейла-Шепли , в котором врачи предлагают совпадения, а больницы отвечают на эти предложения. Он также имеет уникальный наименьший элемент — целочисленное стабильное совпадение, найденное с помощью версии алгоритма Гейла-Шепли, в котором больницы делают предложения. [3]
В соответствии с этим частичным порядком можно определить встречу двух дробных паросочетаний как дробное паросочетание, которое находится как можно ниже в частичном порядке, но при этом доминирует над двумя совпадениями. Для каждого врача и больницы он присваивает этой потенциально совпадающей паре вес, который делает общий вес этой пары и всех лучших пар для одного и того же врача равным большей из соответствующих сумм двух заданных совпаданий. Соединение определяется симметрично. [3]
Приложения
[ редактировать ]Применяя линейное программирование к устойчивому паросочетанию, можно найти стабильное паросочетание минимального или максимального веса. [1] Альтернативные методы решения той же проблемы включают применение проблемы замыкания к частично упорядоченному множеству, полученному из решетки устойчивых паросочетаний . [6] или применить линейное программирование к многограннику порядка этого частичного порядка.
Отношение к многограннику порядка
[ редактировать ]Свойство стабильного многогранника согласования, определять непрерывную дистрибутивную решетку, аналогично определяющему свойству дистрибутивного многогранника , многогранника, в котором покоординатная максимизация и минимизация образуют операции встречи и соединения решетки. [7] Однако операции встречи и соединения для устойчивого совпадающего многогранника определяются иначе, чем покоординатная максимизация и минимизация. Вместо этого порядковый многогранник базового частичного порядка решетки стабильных паросочетаний представляет собой дистрибутивный многогранник, связанный с набором стабильных паросочетаний, но для которого труднее считывать дробное значение, связанное с каждой совпадающей парой. Фактически, стабильный совпадающий многогранник и порядковый многогранник лежащего в его основе частичного порядка очень тесно связаны друг с другом: каждый из них является аффинным преобразованием другого. [8]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Ванде Вейт, Джон Х. (1989), «Линейное программирование приносит семейное счастье», Operations Research Letters , 8 (3): 147–153, doi : 10.1016/0167-6377(89)90041-2 , MR 1007271
- ^ Ратье, Гийом (1996), «О стабильном многограннике брака» (PDF) , Discrete Mathematics , 148 (1–3): 141–159, doi : 10.1016/0012-365X(94)00237-D , MR 1368286
- ^ Перейти обратно: а б с д Рот, Элвин Э .; Ротблюм, Уриэль Г .; Ванде Вейт, Джон Х. (1993), «Стабильные сопоставления, оптимальные назначения и линейное программирование», Mathematics of Operations Research , 18 (4): 803–828, doi : 10.1287/moor.18.4.803 , JSTOR 3690124 , MR 1251681
- ^ Тео, Чунг-Пио; Сетураман, Джей (1998), «Геометрия дробно-устойчивых паросочетаний и ее приложения», Mathematics of Operations Research , 23 (4): 874–891, doi : 10.1287/moor.23.4.874 , MR 1662426
- ^ Кнут, Дональд Э. (1976), Стабильные браки и их связь с другими комбинаторными задачами (PDF) (на французском языке), Монреаль, Квебек: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3 , МР 0488980 . См., в частности, задачу 6, стр. 87–94.
- ^ Ирвинг, Роберт В.; Кожа, Пол; Гасфилд, Дэн (1987), «Эффективный алгоритм для «оптимального» стабильного брака», Journal of the ACM , 34 (3): 532–543, doi : 10.1145/28869.28871 , MR 0904192
- ^ Фельснер, Стефан; Кнауэр, Коля (2011), «Дистрибутивные решетки, многогранники и обобщенные потоки», Европейский журнал комбинаторики , 32 (1): 45–59, doi : 10.1016/j.ejc.2010.07.011 , MR 2727459 .
- ^ Априле, Мануэль; Севальос, Альфонсо; Фаэнца, Юрий (2018), «О двухуровневых многогранниках, возникающих в комбинаторных условиях», SIAM Journal on Discrete Mathematics , 32 (3): 1857–1886, arXiv : 1702.03187 , doi : 10.1137/17M1116684 , MR 3835234