4430
правок
Минимальная бисекция: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
== Основные результаты == | == Основные результаты == | ||
Фейге и Краутхамер [ ] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации O(log | Фейге и Краутхамер [6] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации <math>O(log^2 \; n)</math>, поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до <math>O(log^{1,5} \; n)</math>. | ||
Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом O( | '''Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>. Более конкретно, алгоритм создает для входного графа G бисекцию <math>(S, \bar{S}) \;</math>, стоимость которой не превышает <math>O(log^{1,5} \; n) \cdot b(G)</math>.''' | ||
| Строка 63: | Строка 63: | ||
Теорема 2. Задача о сбалансированном разрезе (и, в частности, о реберном сепараторе может быть приближенно решена за полиномиальное время с коэффициентом O( | '''Теорема 2. Задача о <math>\beta</math>-сбалансированном разрезе (и, в частности, о реберном сепараторе) может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>.''' | ||
Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время | '''Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время <math>n^{O(r)} \;</math> с коэффициентом <math>O(log^{1,5} \; n)</math>.''' | ||
| Строка 72: | Строка 72: | ||
Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, / | '''Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, <math>\beta</math>-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).''' | ||
Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6]. | Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [6]. | ||
== Родственные работы == | == Родственные работы == | ||
