Сепараторы в графах: различия между версиями

[[Сбалансированное сечение|Сбалансированные сечения]]

'''Задача 2 (самый неплотный разрез (относительно произведения))'''

Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение <math>(c( \delta (S))) / (\pi (S) \pi (V \; \backslash \; S))</math>.

Даже если все веса (ребер и вершин) равны 1, нахождение b-сбалансированного сечения с минимальным весом представляет собой NP-полную задачу (для b = 1/2 она превращается в задачу [[бисекция графа|бисекции графа]]). Лейтон и Рао [23, 24] предложили псевдоаппроксимационный алгоритм для решения задачи общего вида.

'''Теорема 1. Существует алгоритм с полиномиальным временем выполнения, который для заданного взвешенного графа <math>G = (v, E, c, \pi), b \le 1/2 \;</math> и <math>b' < min \{ b, 1/3 \} \;</math> находит b'-сбалансированное сечение с весом в O((log n)/(b - b')) больше веса минимального b-сбалансированного сечения.'''

Алгоритм решает задачу нахождения самого разреженного сечения на заданном графе, отбрасывает сегмент с меньшим весом и рекурсивно повторяет операцию на сегменте с большим весом до тех пор, пока вес обоих сегментов самого разреженного сечения не достигнет значения <math>(1 - b') \; \pi (G)</math> или меньше. Теперь сегмент с большим весом, полученный в результате сечения на последней итерации, возвращается алгоритмом как один из сегментов сбалансированного сечения, а все остальные фрагменты графа – как второй сегмент. Поскольку сама по себе задача нахождения самого разреженного сечения является NP-полной, Лейтону и Рао вначале потребовался аппроксимационный алгоритм для ее решения.

'''Теорема 2. Существует алгоритм нахождения самого разреженного сечения для материальных потоков (задача 2) с полиномиальным временем выполнения и коэффициентом аппроксимации O (log p), где p обозначает количество вершин графа с ненулевым весом.'''

'''Теорема 3. Существует алгоритм с полиномиальным временем выполнения, который находит сечение <math>(S : V \; \backslash \; S)</math> с соотношением <math>(c( \delta (S))) / (\pi (S) \pi (V \; \backslash \; S)) \in O(f \; log \; p)</math>, где f – максимальный поток среди всех материальных товарных потоков, а p – количество вершин с ненулевым весом.'''

Доказательство теоремы 3 основано на решении формулировки задачи управления несколькими товарными потоками для линейного программирования и использовании этого решения для построения разреженного сечения.

Шахрохи и Матула [27] предложили теорему о максимальном потоке и минимальном сечении для специального случая задачи управления несколькими товарными потоками и использовали схожий подход на основе линейного программирования для доказательства полученного результата. Верхняя граница O(log n) для произвольного уровня спроса была доказана в работах Аумана и Рабани [6] и Линиала и др. [26]. В обоих случаях решение двойственной линейной программы для управления несколькими товарными потоками интерпретируется как конечная метрика и вкладывается в <math>\ell_1 \;</math> с искажением O (log n) при помощи вложения Бургейна [10]. Полученная в результате метрика <math>\ell_1 \;</math> представляет собой выпуклую комбинацию метрик сечений, из которой может быть извлечено сечение, с коэффициентом разреженности, который должен быть не ниже, чем коэффициент в комбинации.

Узким местом алгоритма поиска сбалансированного сепаратора является решение линейной программы для задачи управления несколькими товарными потоками. Для таких линейных программ было предложено немало быстрых приближенных решений [19, 22, 25]. В большинстве следующих работ алгоритм формирует <math>(1 + \epsilon)</math>-аппроксимацию, скрытая константа которой зависит от <math>\epsilon^{-2} \;</math>. Гарг и Кёнеманн [15], Флейшер [14] и Каракостас [16] предложили эффективные аппроксимационные схемы для задачи управления несколькими товарными потоками и сопутствующих задач с временем выполнения <math>\tilde{O}((k + m) \;m)</math> [15] и <math>\tilde{O} (m^2) \;</math> [14,16]. Бенцур и Карджер [7] предложили O(log n)-аппроксимацию задачи поиска самого разреженного сечения на базе рандомизированного алгоритма нахождения минимального разреза с временем выполнения <math>\tilde{O}(n^2) \;</math>. Наиболее быстрая на данный момент O(log n)-аппроксимация задачи поиска самого разреженного сечения (сбалансированного сепаратора) основана на прямо-двойственном подходе к полуопределенному программированию, предложена Аророй и Кейлом [3] и выполняется за время <math>O(m + n^{3/2})(\tilde{O}(m + n^{3/2})</math>, соответственно). В той же статье приведен алгоритм <math>O(\sqrt{log \; n})</math>-аппроксимации с временем выполнения <math>O(n^2)(\tilde{O}(n^2) \;</math>, соответственно), улучшивший предыдущее время <math>\tilde{O}(n^2) \;</math> алгоритма Ароры и др. [2]. Если <math>O(log^2 \; n)</math>-аппроксимация оказывается достаточной, то самое разреженное сечение может быть найдено за время <math>\tilde{O}(n^{3/2}) \;</math>, а сбалансированный сепаратор – за время <math>\tilde{O}(m + n^{3/2}) \;</math> [17].

Многие задачи можно решить, используя подпрограммы поиска сбалансированного сепаратора или самого разреженного сечения. Коэффициент аппроксимации полученного алгоритма обычно прямо зависит от коэффициента соответствующей подпрограммы. В большинстве случаев граф рекурсивно разбивается на фрагменты сбалансированного размера. Помимо коэффициента аппроксимации O(log n), принадлежащего алгоритму поиска сбалансированного сепаратора, еще один коэффициент O(log n) возникает в силу глубины рекурсии. Ивен и др. [12] улучшили многие результаты на базе алгоритма сбалансированного сепаратора благодаря использованию [[метрика рассеяния|метрик рассеяния]], снизив гарантированный коэффициент аппроксимации с <math>O(log^2 \; n)</math> до O(log n log log n).

• Сбалансированные вершинные сечения. Стоимость сбалансированного сечения может измеряться в терминах веса вершин, удаленных из графа. Алгоритм поиска сбалансированного сепаратора можно легко расширить на такой случай с взвешенными вершинами.

• Бисекция.  Фейге и Краутгамер [7] предложили <math>O( \alpha \; log \; n)</math>-аппроксимацию задачи минимальной бисекции при помощи любого алгоритма <math>\alpha \;</math>-аппроксимации для нахождения минимального сечения.

Ланг и Рао [21] сравнивали вариант поиска самого разреженного сечения из [24] с методами декомпозиции графов для проектирования СБИС.

* ''[[Самое разреженное сечение]]