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

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