Ранг-максимальное распределение

Распределение по максимальному рангу (RM) — это правило справедливого разделения неделимых предметов. Предположим, нам нужно распределить некоторые предметы между людьми. Каждый человек может ранжировать предметы от лучшего к худшему. Правило RM гласит, что мы должны дать как можно большему количеству людей их лучший (№1) товар. При этом мы должны дать как можно большему количеству людей их следующий лучший предмет (№2) и так далее.

В особом случае, когда каждый человек должен получить один элемент (например, когда «элементы» представляют собой задачи и каждая задача должна выполняться одним человеком), проблема называется сопоставлением с максимальным рангом или жадным сопоставлением .

Идея аналогична утилитарному разрезанию торта , цель которого — максимизировать сумму полезностей всех участников. Однако утилитарное правило работает с кардинальными (числовыми) функциями полезности , а правило RM — с порядковыми полезностями (рангами).

Определение

Есть несколько предметов и несколько агентов. У каждого агента есть общий заказ на товары. Агенты могут быть безразличны к некоторым предметам; для каждого агента мы можем разделить элементы на классы эквивалентности, содержащие элементы одного и того же ранга. Например, если отношение предпочтения Алисы равно x > y,z > w , это означает, что первым выбором Алисы является x, который для нее лучше, чем все остальные элементы; Второй выбор Алисы — это y и z, которые в ее глазах одинаково хороши, но не так хороши, как x; и третий выбор Алисы — w, который она считает хуже всех остальных предметов.

Для каждого распределения элементов среди агентов мы строим его ранг-вектор следующим образом. Элемент №1 в векторе — это общее количество предметов, которые являются первым выбором для их владельцев; Элемент №2 — это общее количество предметов, которые являются вторым выбором для их владельцев; и так далее.

— Максимально ранговое распределение это распределение, в котором вектор ранга является максимальным в лексикографическом порядке.

Пример

Три предмета, xy и z, необходимо разделить между тремя агентами, чьи рейтинги:

Алиса: x > y > z
Боб: x > y > z
Карл: y > x > z

В распределении ( x , y , z ) Алиса получает свой первый выбор ( x ), Боб получает свой второй выбор ( y ), а Карл получает свой третий выбор ( z ). Таким образом, ранг-вектор равен (1,1,1).

В распределении ( x , z , y ) и Алиса, и Карл получают свой первый выбор, а Боб получает свой третий выбор. Таким образом, ранг-вектор равен (2,0,1), что лексикографически выше, чем (1,1,1) – он дает большему количеству людей их первый выбор.

Легко проверить, что никакое распределение не создает лексикографически более высокий ранг-вектор. Следовательно, распределение ( x , z , y ) является максимальным по рангу. Точно так же распределение ( z , x , y ) является максимальным по рангу – оно создает тот же вектор ранга (2,0,1).

Алгоритмы

Сочетания RM были впервые изучены Робертом Ирвингом, который назвал их жадными сопоставлениями . Он представил алгоритм, который находит соответствие RM во времени. $O(n^{2}c^{3})$ , где n — количество агентов, а c — наибольшая длина списка предпочтений агента. ^[1]

Позже был найден улучшенный алгоритм, работающий во времени. $O(m\cdot \min(n,C{\sqrt {n}}))$ , где m — общая длина всех списков предпочтений (общее количество ребер в графе), а C — максимальный ранг элемента, используемого в сопоставлении RM (т. е. максимальное количество ненулевых элементов в оптимальном ранговый вектор). ^[2] Алгоритм сводит задачу к сопоставлению максимальной мощности . Интуитивно мы хотели бы сначала найти паросочетание максимальной мощности, используя только ребра ранга 1; затем расширите это паросочетание до паросочетания максимальной мощности, используя только ребра рангов 1 и 2; затем расширите это паросочетание до паросочетания максимальной мощности, используя только ребра рангов 1, 2 и 3; и так далее. Проблема в том, что если мы выберем «неправильное» сопоставление максимальной мощности для ранга 1, мы можем пропустить оптимальное сопоставление для ранга 2. Алгоритм ^[2] решает эту проблему с помощью разложения Дулмаджа-Мендельсона , которое представляет собой разложение, которое использует сопоставление максимальной мощности, но не зависит от того, какое сопоставление выбрано (разложение одинаково для каждого выбранного сопоставления максимальной мощности). Это работает следующим образом.

Пусть G ₁ — подграф G , содержащий только ребра ранга 1 (наивысшего ранга).
Найдите паросочетание максимальной мощности в G ₁ и используйте его, чтобы найти разложение G ₁ на E ₁ , O ₁ и U ₁ .
Одним из свойств разложения является то, что каждое паросочетание максимальной мощности в G ₁ насыщает все вершины в O ₁ и U ₁ . Следовательно, при максимальном по рангу паросочетании все вершины в O ₁ и U ₁ смежны с ребром ранга 1. Таким образом, мы можем удалить из графа все ребра ранга 2 или выше, смежные с любой из этих вершин.
Другое свойство разложения состоит в том, что любое паросочетание максимальной мощности в G ₁ содержит только ребра E ₁ -O ₁ и U ₁ -U ₁ . все остальные ребра (O ₁ -O ₁ и O ₁ -U _{1 ребра).} Следовательно, мы можем удалить из графа
Добавьте к G ₁ все ребра следующего по величине ранга. Если таких ребер нет, остановитесь. В противном случае вернитесь к шагу 2.

Другое решение, использующее сопоставления с максимальным весом , достигает аналогичного времени выполнения: $O(m\cdot \min(n+C,C{\sqrt {n}}))$ . ^[3]

Варианты

Проблема имеет несколько вариантов.

1. При сопоставлении RM с максимальной мощностью цель состоит в том, чтобы найти среди всех различных сопоставлений RM то, которое имеет максимальное количество сопоставлений.

2. При честном сопоставлении цель состоит в том, чтобы найти такое сопоставление максимальной мощности, при котором используется минимальное количество ребер ранга r минимальное количество ребер ранга r , при условии, что - используется −1 и так далее.

Как сопоставление RM с максимальной мощностью, так и справедливое сопоставление можно найти путем сведения к сопоставлению с максимальным весом. ^[3]

3. В задаче сопоставления RM с ограниченными возможностями каждый агент имеет верхнюю пропускную способность, обозначающую верхнюю границу общего количества предметов, которые он должен получить. Каждый элемент имеет верхнюю квоту, обозначающую верхнюю границу количества различных агентов, которым он может быть назначен. Впервые его изучили Мельхорн и Михаил, которые предложили алгоритм с временем выполнения. $O(Cnm\log(n^{2}/m)\log(n))$ . ^[4] Существует улучшенный алгоритм с рантаймом $O(m\cdot \min(B,C{\sqrt {B}}))$ , где B — минимальная сумма квот агентов и сумма квот предметов. Он основан на расширении разложения Галлаи–Эдмондса на многореберные паросочетания. ^[5]

См. также

Ссылки

^ Ирвинг, Роберт В. (2003). Жадные совпадения . Университет Глазго. С. Тр–2003–136. CiteSeerX 10.1.1.119.1747 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Перейти обратно: ^а ^б Ирвинг, Роберт В.; Кавита, Теликепалли ; Мельхорн, Курт; Михаил, Димитриос; Палух, Катажина Е. (1 октября 2006 г.). «Ранг-максимальные совпадения». АКМ Транс. Алгоритмы . 2 (4): 602–610. дои : 10.1145/1198513.1198520 . ISSN 1549-6325 .
^ Перейти обратно: ^а ^б Михаил, Димитриос (10 декабря 2007 г.). «Снижение ранга-максимального до максимального соответствия веса» . Теоретическая информатика . 389 (1): 125–132. дои : 10.1016/j.tcs.2007.08.004 . ISSN 0304-3975 .
^ Курт Мельхорн и Димитриос Михаил (2005). «Сетевые задачи с неполиномиальными весами и приложения» .
^ Палух, Катажина (22 мая 2013 г.). «Соответствия максимального ранга с емкостью». Алгоритмы и сложность . Конспекты лекций по информатике. Том. 7878. Шпрингер, Берлин, Гейдельберг. стр. 324–335. дои : 10.1007/978-3-642-38233-8_27 . ISBN 978-3-642-38232-1 .

[1] Ирвинг, Роберт В. (2003). Жадные совпадения . Университет Глазго. С. Тр–2003–136. CiteSeerX 10.1.1.119.1747 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[:1-2] Перейти обратно: ^а ^б Ирвинг, Роберт В.; Кавита, Теликепалли ; Мельхорн, Курт; Михаил, Димитриос; Палух, Катажина Е. (1 октября 2006 г.). «Ранг-максимальные совпадения». АКМ Транс. Алгоритмы . 2 (4): 602–610. дои : 10.1145/1198513.1198520 . ISSN 1549-6325 .

[:0-3] Перейти обратно: ^а ^б Михаил, Димитриос (10 декабря 2007 г.). «Снижение ранга-максимального до максимального соответствия веса» . Теоретическая информатика . 389 (1): 125–132. дои : 10.1016/j.tcs.2007.08.004 . ISSN 0304-3975 .

[4] Курт Мельхорн и Димитриос Михаил (2005). «Сетевые задачи с неполиномиальными весами и приложения» .

[5] Палух, Катажина (22 мая 2013 г.). «Соответствия максимального ранга с емкостью». Алгоритмы и сложность . Конспекты лекций по информатике. Том. 7878. Шпрингер, Берлин, Гейдельберг. стр. 324–335. дои : 10.1007/978-3-642-38233-8_27 . ISBN 978-3-642-38232-1 .

[1]

[2]

[3]

[4]

[5]