Подбор максимального веса - Maximum weight matching

В Информатика, то максимальное соответствие веса проблема - это проблема нахождения в взвешенный график, а соответствие в котором сумма весов максимальна.

Частным случаем этого является проблема назначения, в котором вход ограничен двудольный граф. Другой частный случай - проблема поиска максимальное соответствие количества элементов на невзвешенном графе: это соответствует случаю, когда все веса ребер одинаковы.

Алгоритмы

Существует ${displaystyle O(V^{2}E)}$ алгоритм времени для поиска максимального совпадения или совпадения максимального веса в недвудольном графе; это связано с Джек Эдмондс, называется дорожки, деревья и цветы метод или просто Алгоритм Эдмондса, и использует двунаправленные края. Обобщение того же метода можно также использовать для поиска максимальные независимые множества в графы без когтей.

Существуют более сложные алгоритмы, которые рассматриваются Дуаном и Петти.^[1] (см. Таблицу III). Их работа предлагает алгоритм аппроксимации для задачи согласования максимального веса, которая выполняется за линейное время для любой фиксированной границы ошибки.

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

1. Дуан, Ран; Петти, Сет (01.01.2014). «Линейное приближение для согласования максимального веса» (PDF). Журнал ACM. Дои:10.1145/2529989.