4551
правка
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Бисекция графа == Постановка задачи == Обзор Минимальна…») |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Минимальная бисекция – это базовое представление семейства задач дискретной оптимизации, имеющих дело с разбиением вершин входного графа. Обычно цель заключается в минимизации количества ребер, соединяющих два отдельных фрагмента графа, при сохранении некоторого контроля над разбиением – например,за счет ограничения количества и/или размера фрагментов. (Это описание соответствует реберному разрезу графа; в случае вершинного разреза употребляются схожие ограничение). Целью задачи о минимальной бисекции является разбиение вершин входного графа на два множества равного размера, такое, чтобы количество ребер, соединяющих эти два множества, было насколько возможно малым. | |||
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм аппроксимации по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего алгоритма аппроксимации со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый алгоритм аппроксимации солиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом. | |||
(Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | |||