4430
правок
Сепараторы в графах: различия между версиями
Материал из WEGA
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 7: | Строка 7: | ||
Более формально: пусть даны неориентированный граф G = (V, E) \; с неотрицательной весовой функцией на ребрах <math>c: E \to \mathbb{R}_+ \;</math> и неотрицательной весовой функцией на вершинах <math>\pi : V \to \mathbb{R}_+ \;</math>, а также константа <math>b \le 1/2 \;</math>. Сечение <math>(S : V \; \backslash \; S)</math> называется b-сбалансированным, или (b, 1 - b)-сепаратором, если <math>b \pi (V) \le \pi (S) le (1 - b) \pi(V) \;</math> (где <math>\pi(S) \;</math> обозначает <math>\sum_{v \in S} \pi (v) \;</math>). | Более формально: пусть даны неориентированный граф <math>G = (V, E) \;</math> с неотрицательной весовой функцией на ребрах <math>c: E \to \mathbb{R}_+ \;</math> и неотрицательной весовой функцией на вершинах <math>\pi : V \to \mathbb{R}_+ \;</math>, а также константа <math>b \le 1/2 \;</math>. Сечение <math>(S : V \; \backslash \; S)</math> называется b-сбалансированным, или (b, 1 - b)-сепаратором, если <math>b \pi (V) \le \pi (S) le (1 - b) \pi(V) \;</math> (где <math>\pi(S) \;</math> обозначает <math>\sum_{v \in S} \pi (v) \;</math>). | ||
| Строка 81: | Строка 81: | ||
Теорема 3. Существует алгоритм с полиномиальным временем исполнения, который находит сечение (S | '''Теорема 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 основано на решении формулировки задачи управления несколькими товарными потоками для линейного программирования и использовании этого решения для построения неплотного сечения. | Доказательство теоремы 3 основано на решении формулировки задачи управления несколькими товарными потоками для линейного программирования и использовании этого решения для построения неплотного сечения. | ||
== Родственные результаты == | == Родственные результаты == | ||
Шахрохи и Матула [ ] предложили теорему о максимальном потоке и минимальном сечении для специального случая задачи управления несколькими товарными потоками и использовали схожий подход на основе линейного программирования для доказательства полученного результата. Верхняя граница O(log n) для произвольного уровня спроса была доказана в работах Аумана и Рабани [ ] и Линиала и др. [26]. В обоих случаях решение двойственной линейной программы для управления несколькими товарными потоками интерпретируется как конечная метрика и вкладывается в | Шахрохи и Матула [27] предложили теорему о максимальном потоке и минимальном сечении для специального случая задачи управления несколькими товарными потоками и использовали схожий подход на основе линейного программирования для доказательства полученного результата. Верхняя граница O(log n) для произвольного уровня спроса была доказана в работах Аумана и Рабани [6] и Линиала и др. [26]. В обоих случаях решение двойственной линейной программы для управления несколькими товарными потоками интерпретируется как конечная метрика и вкладывается в <math>\ell_1 \;</math> с искажением O (log n), используя вложение Бургейна [10]. Полученная в результате метрика <math>\ell_1 \;</math> представляет собой выпуклую комбинацию метрики сечений, из которой может быть извлечено сечение, и коэффициента неплотности (разреженности), который должен быть не ниже, чем коэффициент в сочетании. | ||
