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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Январь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

Максимальный расход и минимальный расход [ править ]

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

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

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

Проблема с товарным потоком товара [ править ]

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

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

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

История [ править ]

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

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

Приблизительные теоремы о максимальном расходе и минимальном сокращении [ править ]

Теоремы о задачах однородных многопродуктовых потоков [ править ]

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

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

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

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

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

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

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

Обобщено на проблему многопродуктового потока продукта [ править ]

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

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

Расширен до задачи направленного многопродуктового потока [ править ]

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

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

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

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

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

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

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

Самые редкие порезы [ править ]

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

Сбалансированные разрезы и разделители [ править ]

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

Проблемы компоновки СБИС [ править ]

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

Проблема с индексом пересылки [ править ]

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

Удаление плоской кромки [ править ]

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

Ссылки [ править ]