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

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

Задача 2 представляет собой наиболее общий случай задачи нахождения самого неплотного сечения, решенной Лейтоном и Рао. Если установить веса всех вершин равными 1, получим однородную версию этой задачи:

'''Задача 3 (самое неплотное сечение (однородное))'''

Самое неплотное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче параллельного управления несколькими товарными потоками (задача 4). Экземпляр задачи управления несколькими товарными потоками определяется на графе с взвешенными ребрами: для каждого из k ''товаров'' обозначаются источник <math>s_i \in V \;</math>, сток <math>t_i \in V \;</math> и спрос <math>D_i \;</math>. Допустимое решение этой задачи определяет для каждого товара функцию потока на E, таким образом направляя поток определенного объема из <math>s_i \;</math> в <math>t_i \;</math>.

Задача 4 может быть решена за полиномиальное время при помощи методов линейного программирования. Она также допускает произвольную аппроксимацию при помощи нескольких более эффективных комбинаторных алгоритмов (см. раздел «Реализация»). Максимальное значение f, для которого возможно управление несколькими товарными потоками, называется [[максимальный поток|максимальным потоком]] для данного экземпляра задачи. ''Минимальным сечением'' является минимальное соотношение <math>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>, где <math>D(S, V \; \backslash \; S) = \sum_{i: | \{ s_i, t_i \} \; \cap \; S | = 1} D_i</math>. Эта двойственная интерпретация приводит нас к самой общей версии задачи – нахождению неоднородного самого неплотного сечения (задача 5).

'''Задача 5 (самое неплотное сечение (неоднородное))'''

(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о самом неплотном сечении»).

 

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

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

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

• Древесная ширина и путевая ширина. Бодлендер и др. [9] показали способ аппроксимации древесной ширины с коэффициентом O(log n) и путевой ширины – с коэффициентом <math>O(log^2 \; n)</math> при помощи сбалансированных вершинных сепараторов.

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

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

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