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

Задача комбинаторной оптимизации

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

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

Ссылки

^ Эдмондс, Джек ; Джайлс, Рик (1977), "Отношение минимума-максимума для субмодулярных функций на графах", Исследования по целочисленному программированию (Proc. Workshop, Бонн, 1975) , Annals of Discrete Mathematics, т. 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
^ ab Флейшер, Лиза; Ивата, Сатору (2000), «Улучшенные алгоритмы минимизации субмодулярных функций и субмодулярного потока», Труды тридцать второго ежегодного симпозиума ACM по теории вычислений , Ассоциация вычислительной техники, стр. 107–116 , doi :10.1145/335305.335318, MR 2114523

[eg-1] Эдмондс, Джек ; Джайлс, Рик (1977), "Отношение минимума-максимума для субмодулярных функций на графах", Исследования по целочисленному программированию (Proc. Workshop, Бонн, 1975) , Annals of Discrete Mathematics, т. 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, MR 2114523