Минимальная бисекция: различия между версиями

Фейге и Краутхамер [ ] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации O(log 2n), поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [ ], авторы улучшили коэффициент до O(log '  и).

Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n). Более конкретно, алгоритм создает для входного графа G бисекцию (S, S), стоимость которой не превышает O(log1:5 n) ■ b(G).

Теорема 2. Задача о сбалансированном разрезе (и, в частности, о реберном сепараторе может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n).

Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время nO(r) с коэффициентом O(log1:5 n).

Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, /3-сбалансированном сечении и запранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).

Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6].