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

Более формально: пусть даны неориентированный граф 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>).

Теорема 3. Существует алгоритм с полиномиальным временем исполнения, который находит сечение (S^ VnS) с соотношением (C(S(S)))/(JT(S)JT(V\ S)) 2 O(f log p), где f – максимальный поток среди всех материальных товарных потоков, а p – количество вершин с ненулевым весом.

Шахрохи и Матула [ ] предложили теорему о максимальном потоке и минимальном сечении для специального случая задачи управления несколькими товарными потоками и использовали схожий подход на основе линейного программирования для доказательства полученного результата. Верхняя граница O(log n) для произвольного уровня спроса была доказана в работах Аумана и Рабани [ ] и Линиала и др. [26]. В обоих случаях решение двойственной линейной программы для управления несколькими товарными потоками интерпретируется как конечная метрика и вкладывается в l\ с искажением O (log n), используя вложение Бургейна [ ]. Полученная в результате метрика l\ представляет собой выпуклую комбинацию метрики сечений, из которой может быть извлечено сечение, и коэффициента неплотности (разреженности), который должен быть не ниже, чем коэффициент в сочетании.