Приближенная теорема о максимальном потоке и минимальном сокращении

Приближенные теоремы о максимальном потоке и минимальном сокращении являются математическими положениями теории сетевых потоков . Приближенные теоремы о максимальном потоке и минимальном сокращении касаются взаимосвязи между максимальным расходом («max-flow») и минимальным сокращением («min-cut») в задаче о потоках многих товаров . Теоремы позволили разработать аппроксимационные алгоритмы для использования при разделении графов и связанных с ними задачах.

Проблема многотоварного потока

«Товаром» в задаче сетевого потока является пара узлов источника и приемника . В задаче о многотоварном потоке существует $k\geq1$ товаров, каждый из которых имеет свой собственный источник. $s_{i}$ , раковина $t_{i}$ , и требовать $D_{i}$ . Цель состоит в том, чтобы одновременно маршрутизировать $D_{\text{i}}$ единиц товара $i$ из $s_{i}$ к $t_{i}$ для каждого $i$ , так что общее количество всех товаров, проходящих через любое ребро, не превышает его пропускную способность. (В случае ненаправленных ребер сумма потоков в обоих направлениях не может превышать пропускную способность ребра). ^[1]В частности, задача потока одного товара (или одного товара) также известна как задача максимального потока . Согласно алгоритму Форда-Фалкерсона , максимальный поток и минимальный поток всегда равны в задаче о потоке одного товара.

Макс.поток и мин.рез.

В задаче о многотоварном потоке максимальный поток — это максимальное значение $f$ , где $f$ — общая доля каждого маршрутизируемого товара, такая что $fD_{\text{i}}$ единицы товара $i$ могут быть одновременно перенаправлены для каждого $i$ без нарушения каких-либо ограничений мощности. min-cut — это минимальное из всех сокращений соотношения $\varphi$ мощности разреза в зависимости от потребности в разрезе.Максимальный поток всегда ограничен сверху минимальным сокращением для задачи многопродуктового потока.

Задача о едином многопродуктовом потоке

В задаче об однородном многотоварном потоке для каждой пары узлов существует товар, и спрос на каждый товар одинаков. (Без ограничения общности, спрос на каждый товар равен единице.) Базовая сеть и мощности произвольны. ^[1]

Проблема многотоварного потока продуктов

В задаче о многотоварном потоке продуктов каждый узел имеет неотрицательный вес. $v\in V$ в графике $G=(V,E)$ . Спрос на товар между узлами $u$ и $v$ является произведением весов узла $u$ и узла $v$ . Задача о равномерном многопродуктовом потоке является частным случаем задачи о многопродуктовом потоке, для которой вес установлен равным 1 для всех узлов. $u\in V$ . ^[1]

Двойственность линейного программирования

В общем, двойственная задача многотоварного потока для графа $G$ — это задача распределения фиксированного количества веса (где веса можно рассматривать как расстояния) ребрам графа $G$ таким образом, чтобы максимизировать совокупное расстояние между источником и стоком. пары. ^[1]

История

Исследование взаимосвязи между максимальным потоком и минимальным сокращением задачи многопродуктового потока вызвало большой интерес после получения результата Форда и Фулкерсона для задач о потоках 1 товара. Ху ^[2]показал, что максимальный поток и минимальный объем всегда равны для двух товаров. Окамура и Сеймур ^[3] проиллюстрировали задачу о потоке четырех товаров с максимальным потоком, равным 3/4, и минимальным сокращением, равным 1. Шахрохи и Матула ^[4] также доказал, что максимальный поток и минимальный разрез равны при условии, что двойственная задача о потоке удовлетворяет определенному условию разреза в задаче о равномерном многопродуктовом потоке. Многие другие исследователи также продемонстрировали конкретные результаты исследований по аналогичным проблемам. ^[5]^[6]^[7]

Для общей задачи сетевого потока максимальный поток находится в пределах $k-$ кратного минимального сокращения, поскольку каждый товар можно оптимизировать отдельно, используя $1/k$ мощности каждого ребра. Это не очень хороший результат, особенно в случае большого количества товаров. ^[1]

Приближенные теоремы о максимальном потоке и минимальном сокращении

Теоремы задач о равномерном многопродуктовом потоке

Есть две теоремы, впервые выдвинутые Томом Лейтоном и Сатишем Рао в 1988 году. ^[8]и затем продлен в 1999 году. ^[1] Теорема 2 дает более точную оценку по сравнению с теоремой 1.

Теорема 1. Для любого $n$ существует $n$ -узловая задача равномерного многопродуктового потока с максимальным потоком $f$ и минимальным разрезом. $\varphi$ для чего $f\leq O\left({\frac {\varphi }{\log n}}\right)$ . ^[1]

Теорема 2. Для любой задачи о равномерном многопродуктовом потоке $\Omega \left({\frac {\varphi }{\log n}}\right)\leq f\leq \varphi$ , где $f$ — максимальный поток и $\varphi$ является минимальным разрезом задачи однородного многопродуктового потока. ^[1]

Чтобы доказать теорему 2, следует обсудить как максимальный поток, так и минимальный разрез. Для максимального потока необходимо использовать методы теории двойственности линейного программирования. Согласно теории двойственности линейного программирования, оптимальная функция расстояния дает общий вес, равный максимальному потоку задачи однородного многопродуктового потока. Для минимальной резки необходимо выполнить трехэтапный процесс: ^[1]^[6]

Этап 1. Рассмотрите двойственную задачу равномерного товарного потока и используйте оптимальное решение для определения графа с метками расстояний на ребрах.

Этап 2. Начиная с источника или приемника, увеличивайте область графа до тех пор, пока не найдете разрез достаточно маленькой емкости, отделяющий корень от его соседа.

Этап 3. Удалите регион и повторяйте процесс этапа 2, пока не будут обработаны все узлы.

Обобщенная задача о многотоварном потоке продуктов

Теорема 3. Для любой задачи о многотоварном потоке с $k$ товарами $\Omega \left({\frac {\varphi }{\log k}}\right)\leq f\leq \varphi$ , где $f$ — максимальный поток и $\varphi$ — это минимальное решение проблемы многотоварного потока продукции. ^[1]

Методика доказательства аналогична доказательству теоремы 2; Основное отличие заключается в учете веса узлов.

Распространено на проблему направленного многопродуктового потока.

В задаче о направленном многопродуктовом потоке каждое ребро имеет направление, и движение потока ограничено в указанном направлении. В задаче о направленном однородном многопродуктовом потоке спрос устанавливается равным 1 для каждого направленного ребра.

Теорема 4. Для любой направленной задачи равномерного многопродуктового потока с $n$ узлами $\Omega \left({\frac {\varphi }{\log n}}\right)\leq f\leq \varphi$ , где $f$ — максимальный поток и $\varphi$ является минимальным разрезом задачи однородного многопродуктового потока. ^[1]

Основное отличие методологии доказательства по сравнению с теоремой 2 заключается в том, что теперь направления ребер необходимо учитывать при определении меток расстояний на этапе 1, а для увеличения областей на этапе 2 более подробную информацию можно найти в . ^[1]

Аналогично, для задачи многотоварного потока продуктов мы имеем следующую расширенную теорему:

Теорема 5. Для любой направленной задачи многотоварного потока с $k$ товарами $\Omega \left({\frac {\varphi }{\log k}}\right)\leq f\leq \varphi$ , где $f$ — максимальный поток и $\varphi$ – это направленный минимиз задачи многопродуктового потока. ^[1]

Приложения к алгоритмам аппроксимации

Приведенные выше теоремы очень полезны для разработки алгоритмов аппроксимации задач NP-трудных , таких как задача о разбиении графа и ее варианты. Ниже мы кратко представляем несколько примеров, а более подробную информацию можно найти у Лейтона и Рао (1999). ^[1]

Самые редкие разрезы

Самый разреженный разрез графа $G=(V,E)$ — это разбиение, для которого минимизировано отношение количества ребер, соединяющих два разбиенных компонента, к произведению чисел узлов обоих компонентов. Это NP-трудная задача, и ее можно аппроксимировать с точностью до $O(\log n)$ коэффициент, используя теорему 2. Кроме того, задача разреженного разреза с взвешенными ребрами, взвешенными узлами или направленными ребрами может быть аппроксимирована в пределах $O(\log p)$ коэффициент, где $p$ — количество узлов с ненулевым весом согласно теоремам 3, 4 и 5.

Сбалансированные разрезы и сепараторы

В некоторых приложениях нам нужно найти небольшой разрез в графе. $G=(V,E)$ который разбивает граф на части почти одинакового размера. Мы обычно называем разрез b-сбалансированным или a $(b,1 - b)$ -сепаратором если (при $b \leq 1/2$ ), $b\pi (V)\leq \pi (U)\leq (1-b)\pi (V)$ где $\pi (U)$ является суммой весов узлов в $U$ . Это также NP-трудная задача. Для этой задачи был разработан аппроксимационный алгоритм: ^[1] и основная идея состоит в том, что $G$ имеет $b$ -сбалансированный разрез размера $S$ , тогда мы находим $b' -$ сбалансированный разрез размера $O\left(S\log {\frac {n}{b}}-b'\right)$ для любого $b',$ где $b' < b$ и $b' \leq 1/3$ . Затем мы повторяем процесс и, наконец, получаем результат, что общий вес ребер в разрезе не превышает $O\left({\frac {S\log n}{b-b'}}\right)$ .

Проблемы с компоновкой СБИС

При проектировании схемы СБИС полезно найти схему минимального размера. Такую проблему часто можно смоделировать как задачу встраивания графа. Цель состоит в том, чтобы найти вложение, для которого область макета минимальна. Найти минимальную площадь макета также NP-сложно. Введен алгоритм аппроксимации ^[1] и результат $O(\log ^{6}n)$ раз оптимально.

Проблема с индексом пересылки

Учитывая $n$ -узловой граф $G$ и вложение $K_{n}$ в $G$ , Chung et al. ^[9]определил индекс пересылки встраивания как максимальное количество путей (каждый из которых соответствует ребру $K_{n}$ ), которые проходят через любой узел $G$ . Цель состоит в том, чтобы найти вложение, которое минимизирует индекс пересылки. Использование подходов встраивания ^[1] можно ограничить индексы узла и пересылки ребер с точностью до $O(\log n)$ -фактор для каждого графа $G$ .

Удаление плоского края

Трагудас ^[10]использует алгоритм аппроксимации сбалансированных сепараторов, чтобы найти набор $O\left((R\log n+{\sqrt {nR}})\log {\frac {n}{R}}\right)$ ограниченной степени $ребра, удаление которых из графа G$ приводит к образованию плоского графа, где $R$ — минимальное количество ребер, которые необходимо удалить из $графа G,$ прежде чем он станет плоским. Остается открытым вопрос, существует ли полилогарифмический $n$ раз оптимальный алгоритм аппроксимации для $R$ . ^[1]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Лейтон, Том; Рао, Сатиш (ноябрь 1999 г.). «Многопродуктовые теоремы о максимальном потоке и минимальном разрезе и их использование при разработке алгоритмов аппроксимации». Журнал АКМ . 46 (6): 787–832. CiteSeerX 10.1.1.640.2995 . дои : 10.1145/331524.331526 . S2CID 18527968 .
^ Ху, ТК (1963). «Мультитоварные сетевые потоки». Исследование операций . 11 (3): 344–360. дои : 10.1287/опре.11.3.344 .
^ Окамура, Х.; Сеймур, П.Д. (1981). «Многотоварные потоки в плоских графах». Журнал комбинаторной теории, серия B. 31 : 75–81. дои : 10.1016/S0095-8956(81)80012-3 .
^ Шахрокри, Ф.; Матула, Дэвид В. (1990). «Задача о максимальном одновременном потоке» . Журнал АКМ . 37 (2): 318–334. дои : 10.1145/77600.77620 . S2CID 4469579 .
^ Кляйн, П.; Плоткин, С.; Рао, С.; Тардос, Э. (1997). «Границы коэффициента минимального сокращения максимального потока для направленных многопродуктовых потоков». Дж. Алгоритмы . 22 : 241–269.
^ Jump up to: ^а ^б Гарг, Н.; Вазарани, В.; Яннакакис, М. (1996). «Приближенные теоремы о минимальном (много) разрезе о максимальном потоке и их приложения». SIAM Journal по вычислительной технике . 25 (2): 235–251. дои : 10.1137/s0097539793243016 .
^ Плиткин С.; Тардос, Э. (1993). «Улучшенные границы коэффициента максимального потока и минимального сокращения для многопродуктовых потоков». Материалы 25-го ежегодного симпозиума ACM по теории вычислений : 691–697.
^ Лейтон, Том; Рао, Сатиш (1988). «Приближенная теорема о максимальном потоке и минимальном разрезе для задач однородного многопродуктового потока с приложениями к аппроксимационным алгоритмам». Материалы 29-го симпозиума IEEE по основам информатики : 422–431.
^ Чанг, ФК; Коффман, Э.Г.; Рейман, Мичиган; Саймон, Бельгия (1987). «Переадресационный индекс сетей связи». Транзакции IEEE по теории информации . 33 (2): 224–232. дои : 10.1109/тит.1987.1057290 .
^ Трагудас, С. (1990). Алгоритмы аппроксимации разбиения СБИС на основе многопродуктовых потоков и других методов (кандидатская диссертация). Департамент компьютерных наук Техасского университета.

[Leighton99-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Лейтон, Том; Рао, Сатиш (ноябрь 1999 г.). «Многопродуктовые теоремы о максимальном потоке и минимальном разрезе и их использование при разработке алгоритмов аппроксимации». Журнал АКМ . 46 (6): 787–832. CiteSeerX 10.1.1.640.2995 . дои : 10.1145/331524.331526 . S2CID 18527968 .

[hu63-2] Ху, ТК (1963). «Мультитоварные сетевые потоки». Исследование операций . 11 (3): 344–360. дои : 10.1287/опре.11.3.344 .

[Okamura_and_Seymour_81-3] Окамура, Х.; Сеймур, П.Д. (1981). «Многотоварные потоки в плоских графах». Журнал комбинаторной теории, серия B. 31 : 75–81. дои : 10.1016/S0095-8956(81)80012-3 .

[Shahrokhi_and_Matula_90-4] Шахрокри, Ф.; Матула, Дэвид В. (1990). «Задача о максимальном одновременном потоке» . Журнал АКМ . 37 (2): 318–334. дои : 10.1145/77600.77620 . S2CID 4469579 .

[Klein97-5] Кляйн, П.; Плоткин, С.; Рао, С.; Тардос, Э. (1997). «Границы коэффициента минимального сокращения максимального потока для направленных многопродуктовых потоков». Дж. Алгоритмы . 22 : 241–269.

[Garg96-6] Jump up to: ^а ^б Гарг, Н.; Вазарани, В.; Яннакакис, М. (1996). «Приближенные теоремы о минимальном (много) разрезе о максимальном потоке и их приложения». SIAM Journal по вычислительной технике . 25 (2): 235–251. дои : 10.1137/s0097539793243016 .

[Plotkin_and_Tardos_93-7] Плиткин С.; Тардос, Э. (1993). «Улучшенные границы коэффициента максимального потока и минимального сокращения для многопродуктовых потоков». Материалы 25-го ежегодного симпозиума ACM по теории вычислений : 691–697.

[Leighton88-8] Лейтон, Том; Рао, Сатиш (1988). «Приближенная теорема о максимальном потоке и минимальном разрезе для задач однородного многопродуктового потока с приложениями к аппроксимационным алгоритмам». Материалы 29-го симпозиума IEEE по основам информатики : 422–431.

[CHUNG87-9] Чанг, ФК; Коффман, Э.Г.; Рейман, Мичиган; Саймон, Бельгия (1987). «Переадресационный индекс сетей связи». Транзакции IEEE по теории информации . 33 (2): 224–232. дои : 10.1109/тит.1987.1057290 .

[TRAGOUDAS90-10] Трагудас, С. (1990). Алгоритмы аппроксимации разбиения СБИС на основе многопродуктовых потоков и других методов (кандидатская диссертация). Департамент компьютерных наук Техасского университета.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]