Устойчивый согласующий многогранник - Stable matching polytope

В математика, экономика, и Информатика, то устойчивый согласующий многогранник или же стабильный брачный многогранник это выпуклый многогранник полученный из решений экземпляра проблема стабильного согласования.[1][2]

Описание

Устойчивый согласованный многогранник - это выпуклый корпус из индикаторные векторы устойчивых соответствий данной задачи. Он имеет размер для каждой пары элементов, которые могут быть сопоставлены, и вершина для каждого стабильного совпадения. Для каждой вершины Декартовы координаты единица для пар, совпадающих в соответствующем совпадении, и ноль для пар, которые не совпадают.[1]

Устойчивый согласованный многогранник имеет полиномиальное число грани. К ним относятся обычные неравенства, описывающие сопоставления без требования стабильности (каждая координата должна быть между 0 и 1, и для каждого элемента, который должен быть сопоставлен, сумма координат для пар, включающих этот элемент, должна быть ровно одной), а также неравенства, ограничивающие результирующее сопоставление должно быть стабильным (для каждой потенциальной совпадающей пары элементов сумма координат совпадений, которые не менее хороши для одного из двух элементов, должна быть не менее единицы). Точки, удовлетворяющие всем этим ограничениям, можно рассматривать как дробные решения релаксация линейного программирования задачи устойчивого согласования.

Целостность

Это теорема Ванде Вате (1989) что многогранник, описываемый перечисленными выше фасетными ограничениями, имеет только описанные выше вершины. В частности, это интегральный многогранник. Это можно рассматривать как аналог теоремы Гаррет Биркофф что аналогичный многогранник Многогранник Биркгофа описывающий набор всех дробных соответствий между двумя наборами, является целым.[3]

Эквивалентный способ сформулировать ту же теорему состоит в том, что каждое дробное сопоставление может быть выражено как выпуклое сочетание интегральных сопоставлений. Тео и Сетураман (1998) докажите это, построив распределение вероятностей для целочисленных паросочетаний, ожидаемое значение можно установить равным любому заданному дробному соответствию. Для этого они выполняют следующие действия:

  • Рассмотрите для каждого элемента на одной стороне задачи стабильного сопоставления (например, врачей в задаче сопоставления врачей больницам) дробные значения, присвоенные парам с элементами на другой стороне (больницы), и отсортируйте эти значения по убыванию. заказывать по предпочтениям этого врача.
  • Разделите единичный интервал на подынтервалы, длина которых равна этим дробным значениям, в отсортированном порядке. Выбор случайного числа в единичном интервале даст случайное совпадение для выбранного врача с вероятностью, равной дробному весу этого совпадения.
  • Симметрично рассмотрим каждый элемент на другой стороне стабильного сопоставления (больницы), отсортируем дробные значения для пар, включающих этот элемент, в порядке возрастания по предпочтению, и построим разбиение единичного интервала, подынтервалы которого имеют эти дробные значения в отсортированный порядок.
  • Можно доказать, что для каждой согласованной пары подинтервалы, связанные с этой парой, одинаковы как в разделе для врача, так и в разделе для больницы в этой паре. Следовательно, выбор одного случайного числа в единичном интервале и использование этого выбора для одновременного выбора больницы для каждого врача и врача для каждой больницы дает сопоставление. Более того, можно показать, что это соответствие является стабильным.

Результирующее случайно выбранное стабильное соответствие выбирает любую конкретную согласованную пару с вероятностью, равной значению дробной координаты этой пары. распределение вероятностей над стабильными паросочетаниями, построенными таким образом, дает представление данного дробного паросочетания в виде выпуклой комбинации целочисленных стабильных паросочетаний.[4]

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

Семейство всех стабильных совпадений образует распределительная решетка, то решетка устойчивых паросочетаний, в которой присоединиться двух сопоставлений дает всем врачам их предпочтение среди назначенных им больниц в двух сопоставлениях, а встреча дает всем больницам их предпочтение.[5]То же самое верно для семейства всех дробных устойчивых паросочетаний, точек устойчивого паросочетания.[3]

В стабильном многограннике сопоставлений можно определить одно сопоставление, которое будет доминировать над другим, если для каждого врача и больницы общее дробное значение, присвоенное совпадениям для этого врача, которые, по крайней мере, так же хороши (для врача), как и эта больница, не менее большой как в первом сопоставлении, так и во втором. частичный заказ о дробных сопоставлениях. Этот частичный порядок имеет уникальный наибольший элемент, целочисленное стабильное соответствие, найденное версией Алгоритм Гейла – Шепли в котором врачи предлагают матчи, а больницы отвечают на предложения. Он также имеет уникальный наименьший элемент - целочисленное стабильное соответствие, обнаруженное версией алгоритма Гейла – Шепли, в котором больницы вносят предложения.[3]

В соответствии с этим частичным порядком, можно определить совпадение двух дробных сопоставлений как дробное сопоставление, которое является как можно более низким в частичном порядке, но при этом доминирует над двумя сопоставлениями. Для каждого врача и больницы он присваивает этой потенциальной согласованной паре вес, который делает общий вес этой пары и всех лучших пар для одного и того же врача равным большему из соответствующих итогов двух заданных сопоставлений. Соединение определяется симметрично.[3]

Приложения

Применяя линейное программирование устойчивому согласованному многограннику можно найти устойчивое согласование минимального или максимального веса.[1] Альтернативные методы решения той же проблемы включают применение проблема закрытия к частично заказанный набор полученный из решетка устойчивых паросочетаний,[6] или применяя линейное программирование к многогранник порядка этого частичного порядка.

Связь с многогранником порядка

Свойство устойчивого согласованного многогранника задавать непрерывную распределительную решетку аналогично определяющему свойству многогранника распределительный многогранник, многогранник, в котором покоординатная максимизация и минимизация образуют операции пересечения и соединения решетки.[7] Однако операции пересечения и соединения для устойчивого согласованного многогранника определяются иначе, чем покоординатная максимизация и минимизация. Вместо этого порядковый многогранник лежащего в основе частичного порядка решетка устойчивых паросочетаний предоставляет распределительный многогранник, связанный с набором стабильных сопоставлений, но такой, для которого труднее считывать дробное значение, связанное с каждой сопоставленной парой. Фактически, устойчивый согласованный многогранник и многогранник порядка нижележащего частичного порядка очень тесно связаны друг с другом: каждый из них является аффинное преобразование другого.[8]

Рекомендации

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