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

'''Теорема 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-сбалансированного сечения.'''

'''Теорема 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 – количество вершин с ненулевым весом.'''

Узким местом алгоритма поиска сбалансированного сепаратора является решение линейной программы для задачи управления несколькими товарными потоками. Для таких линейных программ было предложено немало быстрых приближенных решений [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].