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

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

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

Арора и др. [5] предложили алгоритм псевдоаппроксимации с коэффициентом <math>O(\sqrt {log \; n})</math> для нахождения сбалансированных сепараторов в случае однородных либо взвешенных материальных потоков, основанный на полуопределенной релаксации. Для неоднородной версии лучшую границу <math>O(\sqrt {log \; n} \; log \; log \; n)</math> демонстрирует алгоритм Ароры и др. [4]. Хот и Вишной [18] показали, что для неоднородной версии задачи полуопределенная релаксация [5] имеет разрыв целостности не менее <math>(log \; log \; n)^{1/6 - \delta}</math> для любого <math>\delta > 0 \;</math> и, более того, согласно их гипотезе об уникальной игре, (псевдо)аппроксимация задачи о сбалансированном сепараторе с любым константным коэффициентом является NP-полной. Краутгамер и Рабани [20] усилили разрыв целостности в задаче полуопределенного программирования (SDP) до <math>\Omega (log \; log \; n)</math>. Деванур и др. [11] продемонстрировали разрыв целостности в размере <math>\Omega (log \; log \; n)</math> для формулировки задачи SDP даже в однородном случае.

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

• Проектирование СБИС. Бхатт и Лейтон [8] изучали несколько задач оптимизации для проектирования СБИС. Рекурсивное разбиение при помощи алгоритма поиска сбалансированного сепаратора ведет к созданию полилогарифмических алгоритмов аппроксимации для нахождения количества пересечений, минимальной площади размещения схемы и других показателей.