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

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

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

Примеры

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

от максимального веса набор MU _{Аналогично, если} и MV _{каждое ребро имеет вес, то независимый} является сопоставлением максимального веса в G .

Алгоритмы

Существует несколько алгоритмов с полиномиальным временем взвешенного пересечения матроидов с разным временем выполнения. Время выполнения указано в терминах $n$ - количество элементов в общем базовом наборе, $r$ - максимум между рангами двух матроидов, $T$ - количество операций, необходимых для оракула поиска цепей , и $k$ - количество элементов в пересечении (в случае, если мы хотим найти пересечение определенного размера $k$ ).

Алгоритм Эдмондса использует линейное программирование и многогранники. ^[1]
Лоулера . Алгоритм ^[2]
Алгоритм Ири и Томизавы ^[3]
Андраша Франка Алгоритм ^[4] использует $O(n^{3}T)$ арифметические операции.
Алгоритм Орлина и Ванде-Вейта. ^[5]
Алгоритм Каннингема ^[6] требует $O(r^{1.5}nT)$ операции на обычных матроидах и $O(nr^{2}\log {r})$ операции над линейным матроидом для двух r матриц размером на n .
Брезовец, Корнуэхос и Гловер ^[7] представить два алгоритма взвешенного пересечения матроидов.
- Первый алгоритм требует, чтобы все веса были целыми числами, и находит пересечение мощностей. $k$ вовремя $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ .
- Второй алгоритм работает во времени $O(nr\cdot (\log {n}+r+T))$ .
Хуан, Какимура и Камияма ^[8] покажите, что задача пересечения взвешенных матроидов может быть решена путем решения W экземпляров задачи пересечения невзвешенных матроидов, где W — наибольший заданный вес, предполагая, что все заданные веса являются целыми. Этот алгоритм работает быстрее, чем предыдущие алгоритмы, когда W мало. Они также представляют алгоритм аппроксимации, который находит e -приближенное решение путем решения $O(\epsilon ^{-1}\log {r})$ примеры задачи пересечения невзвешенных матроидов, где r — меньший ранг двух входных матроидов.
Гош, Гурджар и Радж ^[9] изучить сложность пересечения матроидов во время выполнения в модели параллельных вычислений .
Берчи, Кирай, Ямагути и Ёкой ^[10] представить сильно полиномиальные алгоритмы для взвешенного пересечения матроидов с использованием более ограниченных оракулов.

Расширения

Максимизация веса в зависимости от мощности

В варианте взвешенного пересечения матроидов, называемом «(Pk ₎ », цель состоит в том, чтобы найти общий независимый набор с максимально возможным весом среди всех таких наборов с мощностью k , если такой набор существует. Этот вариант также может быть решен за полиномиальное время. ^[7]

Три матроида

Задача пересечения матроидов становится NP-сложной , если в ней участвуют три матроида вместо двух.

Одно из доказательств этого результата о сложности использует редукцию гамильтоновой задачи о пути в ориентированных графах . Учитывая ориентированный граф G с n вершинами и указанными узлами s и t , проблема гамильтонова пути — это проблема определения, существует ли простой путь длины n - 1, который начинается в s и заканчивается в t . Без ограничения общности можно предположить, что s не имеет входящих ребер, а t не имеет исходящих ребер. Тогда гамильтонов путь существует тогда и только тогда, когда существует набор из n - 1 элементов в пересечении трех матроидов на множестве ребер графа: два матроида разбиения, гарантирующие, что входящая и исходящая степень выбранного ребра оба набора не более одного, а графический матроид неориентированного графа формируется путем забывания ориентации ребер в G , гарантируя, что выбранный набор ребер не имеет циклов. ^[11]

Матроидная четность

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

Ценные матроиды

Оцененный матроид — это матроид, снабженный функцией ценности v на множестве своих баз со следующим свойством обмена : для любых двух различных базисов $A$ и $B$ , если $a\in A\setminus B$ , то существует элемент $b\in B\setminus A$ такой, что оба $(A\setminus \{a\})\cup \{b\}$ и $(B\setminus \{b\})\cup \{a\}$ являются базами, а: $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ .

Учитывая взвешенный двудольный граф G = ( X + Y , E ) и два оцененных матроида, один на X набором B _X и оценкой v _X , и один на Y с базой BY _Y и оценкой v _{с базовым} , задача независимого назначения с оценкой - это проблема поиска паросочетания M в G , такого, что MX _X (подмножество , соответствующее M ) является базой в B _X , M _Y является базой в BY _{, и при этом} сумма $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ максимизируется. Задача пересечения взвешенных матроидов — это особый случай, в котором оценки матроидов постоянны, поэтому мы стремимся только максимизировать $w(M)$ подчиненный MX _и является базой в B _X . M _Y базой BY _в является ^[14] Мурота представляет алгоритм решения этой задачи с полиномиальным временем. ^[15]

См. также

Разбиение Матроида на разделы — сопутствующая проблема.

Ссылки

^ Jump up to: ^а ^б Эдмондс, Джек (1970), «Субмодулярные функции, матроиды и некоторые многогранники», у Р. Гая; Х. Ханам; Н. Зауэр; Дж. Шонхейм (ред.), Комбинаторные структуры и их приложения (Труды конференции в Калгари, 1969 г.) , Гордон и Брич, Нью-Йорк, стр. 69–87 . Перепечатано в M. Junger et al. (Ред.): Комбинаторная оптимизация (Edmonds Festschrift), LNCS 2570, стр. 1126, Springer-Verlag, 2003.
^ Лоулер, Юджин Л. (1975), «Алгоритмы пересечения матроидов», Mathematical Programming , 9 (1): 31–56, doi : 10.1007/BF01681329 , S2CID 206801650
^ Ири, Масао, Нобуаки (1976). Алгоритм поиска оптимального «независимого назначения» » . Японского общества исследования операций . 19 (1): Журнал « 32–57 .
^ Франк, Андраш (1981), «Алгоритм пересечения взвешенных матроидов», Journal of Algorithms , 2 (4): 328–336, doi : 10.1016/0196-6774(81)90032-8
^ Орлин, Джеймс Б.; Вандевейт, Джон (1983). Об «первичном» алгоритме пересечения матроидов (Рабочий документ Школы менеджмента Слоана № 1446-83). hdl : 1721.1/2050 .
^ Каннингем, Уильям Х. (1 ноября 1986 г.). «Улучшенные границы для алгоритмов разделения и пересечения матроидов» . SIAM Journal по вычислительной технике . 15 (4): 948–957. дои : 10.1137/0215066 . ISSN 0097-5397 .
^ Jump up to: ^а ^б Брезовец, Карл; Корнюжоль, Жерар ; Гловер, Фред (1986), «Два алгоритма взвешенного пересечения матроидов», Mathematical Programming , 36 (1): 39–53, doi : 10.1007/BF02591988 , S2CID 34567631
^ Хуанг, Цзянь-Чунг; Какимура, Наонори; Камияма, Наоюки (01 сентября 2019 г.). «Точные и аппроксимационные алгоритмы пересечения взвешенных матроидов» . Математическое программирование . 177 (1): 85–112. дои : 10.1007/s10107-018-1260-x . hdl : 2324/1474903 . ISSN 1436-4646 . S2CID 254138118 .
^ Гош, Суманта; Гурджар, Рохит; Радж, Рошан (01 января 2022 г.), «Детерминистическая параллельная редукция от поиска взвешенных пересечений матроидов к принятию решения» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2022 г. , Труды Общества промышленной и прикладной математики, стр. 1013–1035, doi : 10.1137/1.9781611977073.44 , ISBN. 978-1-61197-707-3 , S2CID 245799113 , получено 28 ноября 2022 г.
^ Берчи, Кристоф; Кирай, Тамаш; Ямагучи, Ютаро; Ёкои, Ю (28 сентября 2022 г.). «Пересечение матроидов под ограниченными оракулами». arXiv : 2209.14516 [ cs.DS ].
^ Уэлш, DJA (2010) [1976], Теория Матроидов , Courier Dover Publications, стр. 131, ISBN 9780486474397 .
^ Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов» , Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106 .
^ Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .
^ Мурота, Кадзуо (1 ноября 1996 г.). «Оцененное пересечение матроидов I: критерии оптимальности» . SIAM Journal по дискретной математике . 9 (4): 545–561. дои : 10.1137/S0895480195279994 . ISSN 0895-4801 .
^ Мурота, Кадзуо (ноябрь 1996 г.). «Пересечение оцененного матроида II: алгоритмы» . SIAM Journal по дискретной математике . 9 (4): 562–576. дои : 10.1137/S0895480195280009 . ISSN 0895-4801 .

Дальнейшее чтение

Айгнер, Мартин; Даулинг, Томас (1971), «Теория соответствия для комбинаторной геометрии», Труды Американского математического общества , 158 (1): 231–245, doi : 10.1090/S0002-9947-1971-0286689-5 .
Фредериксон, Грег Н.; Шринивас, Мандаям А. (1989), «Алгоритмы и структуры данных для расширенного семейства задач пересечения матроидов» (PDF) , SIAM Journal on Computing , 18 (1): 112–138, doi : 10.1137/0218008 , заархивировано из оригинал от 22 сентября 2017 г.
Габоу, Гарольд Н .; Тарьян, Роберт Э. (1984), «Эффективные алгоритмы для семейства задач пересечения матроидов», Journal of Algorithms , 5 (1): 80–131, doi : 10.1016/0196-6774(84)90042-7 ..

[:0-1] Jump up to: ^а ^б Эдмондс, Джек (1970), «Субмодулярные функции, матроиды и некоторые многогранники», у Р. Гая; Х. Ханам; Н. Зауэр; Дж. Шонхейм (ред.), Комбинаторные структуры и их приложения (Труды конференции в Калгари, 1969 г.) , Гордон и Брич, Нью-Йорк, стр. 69–87 . Перепечатано в M. Junger et al. (Ред.): Комбинаторная оптимизация (Edmonds Festschrift), LNCS 2570, стр. 1126, Springer-Verlag, 2003.

[2] Лоулер, Юджин Л. (1975), «Алгоритмы пересечения матроидов», Mathematical Programming , 9 (1): 31–56, doi : 10.1007/BF01681329 , S2CID 206801650

[3] Ири, Масао, Нобуаки (1976). Алгоритм поиска оптимального «независимого назначения» » . Японского общества исследования операций . 19 (1): Журнал « 32–57 .

[4] Франк, Андраш (1981), «Алгоритм пересечения взвешенных матроидов», Journal of Algorithms , 2 (4): 328–336, doi : 10.1016/0196-6774(81)90032-8

[5] Орлин, Джеймс Б.; Вандевейт, Джон (1983). Об «первичном» алгоритме пересечения матроидов (Рабочий документ Школы менеджмента Слоана № 1446-83). hdl : 1721.1/2050 .

[6] Каннингем, Уильям Х. (1 ноября 1986 г.). «Улучшенные границы для алгоритмов разделения и пересечения матроидов» . SIAM Journal по вычислительной технике . 15 (4): 948–957. дои : 10.1137/0215066 . ISSN 0097-5397 .

[:1-7] Jump up to: ^а ^б Брезовец, Карл; Корнюжоль, Жерар ; Гловер, Фред (1986), «Два алгоритма взвешенного пересечения матроидов», Mathematical Programming , 36 (1): 39–53, doi : 10.1007/BF02591988 , S2CID 34567631

[8] Хуанг, Цзянь-Чунг; Какимура, Наонори; Камияма, Наоюки (01 сентября 2019 г.). «Точные и аппроксимационные алгоритмы пересечения взвешенных матроидов» . Математическое программирование . 177 (1): 85–112. дои : 10.1007/s10107-018-1260-x . hdl : 2324/1474903 . ISSN 1436-4646 . S2CID 254138118 .

[9] Гош, Суманта; Гурджар, Рохит; Радж, Рошан (01 января 2022 г.), «Детерминистическая параллельная редукция от поиска взвешенных пересечений матроидов к принятию решения» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2022 г. , Труды Общества промышленной и прикладной математики, стр. 1013–1035, doi : 10.1137/1.9781611977073.44 , ISBN. 978-1-61197-707-3 , S2CID 245799113 , получено 28 ноября 2022 г.

[10] Берчи, Кристоф; Кирай, Тамаш; Ямагучи, Ютаро; Ёкои, Ю (28 сентября 2022 г.). «Пересечение матроидов под ограниченными оракулами». arXiv : 2209.14516 [ cs.DS ].

[11] Уэлш, DJA (2010) [1976], Теория Матроидов , Courier Dover Publications, стр. 131, ISBN 9780486474397 .

[12] Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов» , Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106 .

[13] Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .

[14] Мурота, Кадзуо (1 ноября 1996 г.). «Оцененное пересечение матроидов I: критерии оптимальности» . SIAM Journal по дискретной математике . 9 (4): 545–561. дои : 10.1137/S0895480195279994 . ISSN 0895-4801 .

[15] Мурота, Кадзуо (ноябрь 1996 г.). «Пересечение оцененного матроида II: алгоритмы» . SIAM Journal по дискретной математике . 9 (4): 562–576. дои : 10.1137/S0895480195280009 . ISSN 0895-4801 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]