Субмодульный поток

В теории оптимизации комбинаторной субмодульный поток — это общий класс задач оптимизации, который включает в себя в качестве частных случаев задачу потока с минимальной стоимостью , пересечение матроидов минимального веса и задачу вычисления диджойна во взвешенном ориентированном графе . Первоначально он был сформулирован Джеком Эдмондсом и Риком Джайлсом. ^[1] и может быть решена за полиномиальное время . ^[2]^[3]^[4]

В классической задаче о потоке с минимальной стоимостью входными данными является сеть потоков с заданными мощностями, которые определяют нижний и верхний пределы количества потока на ребро, а также затраты на единицу потока вдоль каждого ребра. Цель состоит в том, чтобы найти систему величин потока, которая подчиняется пропускным способностям на каждом ребре, подчиняется закону Кирхгофа , согласно которому общая сумма потока в каждую вершину равна общей сумме потока на выходе и имеет минимальную общую стоимость. В субмодулярном потоке также задана субмодулярная функция множества на множествах вершин графа. Вместо того, чтобы подчиняться закону Кирхгофа, требуется, чтобы для каждого набора вершин избыточный поток (функция, отображающая набор в его разницу между входным и выходным потоком) не превышал значения, заданного субмодулярной функцией. ^[4]

Ссылки

^ Эдмондс, Джек ; Джайлс, Рик (1977), «Отношение мин-макс для субмодулярных функций на графах», Исследования по целочисленному программированию (Proc. Workshop, Бонн, 1975) , Анналы дискретной математики, том. 1, Северная Голландия, Амстердам, стр. 185–204, MR 0460169.
^ Гретшель, М.; Ловас, Л.; Шрийвер, А. (1981), «Метод эллипсоидов и его последствия в комбинаторной оптимизации», Combinatorica , 1 (2): 169–197, doi : 10.1007/BF02579273 , MR 0625550 , S2CID 43787103
^ Габоу, Гарольд Н. (1993), «Структура алгоритмов масштабирования стоимости для задач субмодульного потока», Труды 34-го ежегодного симпозиума по основам информатики (FOCS), Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , IEEE Computer Society, стр. 449–458, doi : 10.1109/SFCS.1993.366842 , S2CID 32162097.
^ Перейти обратно: ^а ^б Флейшер, Лиза; Ивата, Сатору (2000), «Улучшенные алгоритмы минимизации субмодульных функций и субмодульного потока», Труды тридцать второго ежегодного симпозиума ACM по теории вычислений , Ассоциация вычислительной техники, стр. 107–116, doi : 10.1145/335305.335318 , МР 2114523

[eg-1] Эдмондс, Джек ; Джайлс, Рик (1977), «Отношение мин-макс для субмодулярных функций на графах», Исследования по целочисленному программированию (Proc. Workshop, Бонн, 1975) , Анналы дискретной математики, том. 1, Северная Голландия, Амстердам, стр. 185–204, MR 0460169.

[gls-2] Гретшель, М.; Ловас, Л.; Шрийвер, А. (1981), «Метод эллипсоидов и его последствия в комбинаторной оптимизации», Combinatorica , 1 (2): 169–197, doi : 10.1007/BF02579273 , MR 0625550 , S2CID 43787103

[gabow-3] Габоу, Гарольд Н. (1993), «Структура алгоритмов масштабирования стоимости для задач субмодульного потока», Труды 34-го ежегодного симпозиума по основам информатики (FOCS), Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , IEEE Computer Society, стр. 449–458, doi : 10.1109/SFCS.1993.366842 , S2CID 32162097.

[fi-4] Перейти обратно: ^а ^б Флейшер, Лиза; Ивата, Сатору (2000), «Улучшенные алгоритмы минимизации субмодульных функций и субмодульного потока», Труды тридцать второго ежегодного симпозиума ACM по теории вычислений , Ассоциация вычислительной техники, стр. 107–116, doi : 10.1145/335305.335318 , МР 2114523

[1]

[2]

[3]

[4]