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

Даже если все веса (ребер и вершин) равны 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> представляет собой выпуклую комбинацию метрик сечений, из которой может быть извлечено сечение, с коэффициентом неплотности (разреженности), который должен быть не ниже, чем коэффициент в комбинации.

Арора и др. [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].

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

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

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

* ''[[Самое неплотное сечение]]