WikiDer > Пересечение матроидов

Matroid intersection

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

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

пример

Позволять г = (U,V,E) быть двудольный граф. Можно определить раздел матроид MU на земле установлен E, в котором набор ребер независим, если никакие два ребра не имеют одинаковых конечных точек в U. Аналогичным образом можно определить матроид MV в котором набор ребер независим, если никакие два ребра не имеют одинаковых конечных точек в V. Любой набор ребер, независимых в обоих MU и MV обладает тем свойством, что никакие два его ребра не имеют общей конечной точки; то есть это соответствие. Таким образом, наибольший общий независимый набор MU и MV это максимальное соответствие в г.

Расширение

Проблема пересечения матроидов становится NP-жесткий когда задействовано три матроида вместо двух.

Одно доказательство этого результата твердости использует сокращение от Гамильтонов путь проблема в ориентированные графы. Учитывая ориентированный граф г с участием п вершины и указанные узлы s и т, проблема гамильтонова пути - это проблема определения того, существует ли простой путь длины п - 1, который начинается в s и заканчивается в т. Без ограничения общности можно предположить, что s не имеет входящих ребер и т не имеет исходящих ребер. Тогда гамильтонов путь существует тогда и только тогда, когда существует набор п - 1 элемент на пересечении трех матроидов на множестве ребер графа: два матроида разбиения, гарантирующих, что внутренняя и исходящая степени выбранного набора ребер равны не более чем одному, и графический матроид из неориентированный граф формируется за счет забвения ориентации краев в г, гарантируя, что выбранный набор кромок не имеет циклов (Валлийский 2010).

Еще одна вычислительная проблема на матроидах - проблема четности матроидов, был сформулирован Лоулер (1976) как общее обобщение пересечения матроидов и недвудольного сопоставления графов, однако, хотя это может быть решено за полиномиальное время для линейные матроиды, это NP-сложно для других матроидов и требует экспоненциального времени в матроид оракул модель (Дженсен и Корте 1982).

использованная литература

  • Брезовец, Карл; Cornuéjols, Жерар; Гловер, Фред (1986), "Два алгоритма взвешенного пересечения матроидов", Математическое программирование, 36 (1): 39–53, Дои:10.1007 / BF02591988.
  • Айгнер, Мартин; Доулинг, Томас (1971), "Теория согласования для комбинаторных геометрий", Труды Американского математического общества, 158 (1): 231–245, Дои:10.1090 / S0002-9947-1971-0286689-5.
  • Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», у Р. Гая; Х. Ханам; Н. Зауэр; J. Schonheim (ред.), Комбинаторные структуры и их приложения (Proc. 1969 Calgary Conference), Гордон и Брич, Нью-Йорк, стр. 69–87.. Перепечатано в M. Jünger et al. (Ред.): Комбинаторная оптимизация (Эдмондс Фестшрифт), LNCS 2570, стр. 1126, Springer-Verlag, 2003.
  • Франк, Андраш (1981), "Взвешенный алгоритм пересечения матроидов", Журнал алгоритмов, 2 (4): 328–336, Дои:10.1016/0196-6774(81)90032-8.
  • Фредериксон, Грег Н .; Шринивас, Мандаям А. (1989), «Алгоритмы и структуры данных для расширенного семейства задач пересечения матроидов», SIAM Журнал по вычислениям, 18 (1): 112–138, Дои:10.1137/0218008.
  • Габоу, Гарольд Н .; Тарджан, Роберт Э. (1984), «Эффективные алгоритмы для семейства задач пересечения матроидов», Журнал алгоритмов, 5 (1): 80–131, Дои:10.1016/0196-6774(84)90042-7.
  • Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, Г-Н 0646772.
  • Лоулер, Юджин Л. (1975), «Алгоритмы пересечения матроидов», Математическое программирование, 9 (1): 31–56, Дои:10.1007 / BF01681329.
  • Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности Matroid», Комбинаторная оптимизация: сети и матроиды, Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, Г-Н 0439106.
  • Валлийский, Д. Дж. А. (2010) [1976], Матроид Теория, Courier Dover Publications, стр. 131, ISBN 9780486474397.