4551
правка
Минимальная бисекция: различия между версиями
Материал из WEGA
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 42: | Строка 42: | ||
Специальный случай f$ = 2/3 часто называется задачей о реберном сепараторе (EDGE-SEPARATOR). | Специальный случай f$ = 2/3 часто называется задачей о реберном сепараторе (EDGE-SEPARATOR). | ||
В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза (S, S), такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число r > 2 – или разделить граф на r фрагментов размерами k1,... , kr, где числа ki заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами. | |||
Задача 3. Заранее заданное разбиение | |||
Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа k1, ... , kr, такие, что Pi ki = j Vj. | |||
Требуется: найти разбиение V = V 1 • • • U Vr графа G с j V i j = ki для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам Vi, насколько возможно мал. | |||
== Основные результаты == | |||
Фейге и Краутхамер [ ] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации 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). | |||
Для всех трех вышеприведенных задач коэффициент аппроксимации можно улучшить до O(log n) для семейства графов, не включающих фиксированный минор (в частности, сюда входят некоторые планарные графы). Для простоты здесь приводятся результаты для задачи о минимальной бисекции. | |||
Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, /3-сбалансированном сечении и запранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n). | |||
Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6]. | |||
== Родственные работы == | |||
