Приоритетное соответствие - Priority matching

В теория графов, а соответствие приоритета (также называемый: соответствие максимального приоритета) это соответствие что максимизирует количество вершин с высоким приоритетом, участвующих в сопоставлении. Формально нам дан график грамм = (V, E) и разбиение множества вершин V в некоторые k подмножества, V1, ..., Vk, называется классы приоритета. Приоритетное сопоставление - это сопоставление, которое среди всех возможных сопоставлений насыщает наибольшее количество вершин из V1; при этом он насыщает наибольшее количество вершин из V2; при этом он насыщает наибольшее количество вершин из V3; и так далее.

Приоритетные соответствия были введены Элвин Рот, Тайфун Сонмез и Утку Унвер[1] в контексте обмен почек. В этой задаче вершины представляют собой пары пациент-донор, и каждое ребро представляет собой взаимную медицинскую совместимость. Например, граница между парой 1 и парой 2 указывает, что донор 1 совместим с пациентом 2, а донор 2 совместим с пациентом 1. Классы приоритета соответствуют медицинскому приоритету среди пациентов. Например, некоторые пациенты находятся в более тяжелом состоянии, поэтому их необходимо сначала сопоставить. Рот, Сонмез и Унвер предположили, что каждый приоритетный класс содержит одну вершину, т. Е. Классы приоритета вызывают общий заказ среди пар.

Позже Ясунори Окумура[2] распространил работу на классы приоритета, которые могут содержать любое количество вершин. Он также показал, как эффективно находить соответствие приоритетов, используя алгоритм для сопоставление максимальной мощности, со сложностью выполнения O (| V | | E | + | V |2 журнал | V |).

Джонатан С. Тернер[3] представили вариант метода увеличения пути (Алгоритм Эдмондса ), который находит соответствие приоритета за время O (| V | | E |). Позже он нашел более быстрый алгоритм для двудольные графы: алгоритм работает за время O (k | E | | V |1/2).[4]

Смотрите также

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

  1. ^ Рот, Элвин Э .; Сёнмез, Тайфун; Утку Юнвер, М. (01.12.2005). «Парный обмен почек». Журнал экономической теории. 125 (2): 151–188. Дои:10.1016 / j.jet.2005.04.004. ISSN  0022-0531. S2CID  583399.
  2. ^ Окумура, Ясунори (01.11.2014). «Еще раз о приоритетных сопоставлениях». Игры и экономическое поведение. 88: 242–249. Дои:10.1016 / j.geb.2014.10.007. ISSN  0899-8256.
  3. ^ Тернер, Джонатан (28 декабря 2015 г.). «Максимальное приоритетное соответствие». arXiv:1512.08555 [cs.DS ].
  4. ^ Тернер, Джонатан (31 декабря 2015 г.). «Более быстрые сопоставления с максимальным приоритетом в двудольных графах». arXiv:1512.09349 [cs.DS ].