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

Узким местом алгоритма поиска сбалансированного сепаратора является решение линейной программы для задачи управления несколькими товарными потоками. Для таких линейных программ было предложено немало быстрых приближенных решений [19, 22, 25]. В большинстве следующих работ алгоритм формирует (1 + e)-аппроксимацию, скрытая константа которой зависит от e~2. Гарг и Конеманн [ ], Флейшер [14] и Каракостас [16] предложили эффективные схемы аппроксимации для задачи управления несколькими товарными потоками и сопутствующих задач с временем исполнения 6((k + m)m) [ ] и 6{m2) [14,16]. Бенцур и Карджер [7] предложили O(log n)-аппроксимацию задачи поиска самого неплотного сечения на базе рандомизированного алгоритма нахождения минимального разреза с временем исполнения O(n2). Наиболее быстрая на данный момент O(log n)-аппроксимация задачи поиска самого неплотного сечения (сбалансированного сепаратора) основана на прямо-двойственном подходе к полуопределенному программированию, предложена Аророй и Кейлом [3] и исполняется за время O(m + пш)(б(т + n3/2), соответственно). В той же статье приведен алгоритм O(log n)-аппроксимации с временем исполнения О(и2) (6(и2), соответственно), улучшивший предыдущее время 6(и2) Ароры и др. [ ]. Если O(log n)-аппроксимация оказывается достаточной, то самое неплотное сечение может быть найдено за время 6(и3/2), а сбалансированный сепаратор – за время 6(m + n3/2) [17].