4817
правок
Самый неплотный разрез: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Разрез с минимальным отношением ''(Minimum ratio cut)'' == Постановка задачи == Неформально в задаче о самом неплотном разрезе (Sparsest Cut) цель заключается в том, чтобы разбить заданный граф на две или несколько больших частей, удалив при...») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Формально, если задан граф G = (V, E), то разреженность или реберное расширение непустого множества S | Формально, если задан граф G = (V, E), то ''разреженность'' или ''реберное расширение'' непустого множества <math>S \subset V, |S| \le \frac{1}{2} |V|</math>, определяется следующим образом: | ||
<math>\alpha(S) = \frac{|E(S), V \backslash S|}{|S|}</math>. | |||
Разреженность графа, <math>\alpha(G)</math>, определяется по формуле: | |||
Задача о самом неплотном разрезе состоит в том, чтобы найти подмножество S | <math>\alpha(G) = min_{S \subset V, |S| \le \frac{1}{2} |V|} \; \alpha(S)</math>. | ||
Задача о самом неплотном разрезе состоит в том, чтобы найти подмножество <math>S \subset V</math> с минимальной разреженностью и определить разреженность графа. | |||
Первый аппроксимационный алгоритм для задачи Sparsest Cut был разработан Лейтоном и Рао в 1988 году [13]. Применяя релаксацию линейного программирования для данной задачи, они получили аппроксимацию с коэффициентом O(log n), где n – размер входного графа. Впоследствии Арора, Рао и Вазирани [4] улучшили алгоритм Лейтона и Рао с помощью релаксации полуопределенного программирования, аппроксимировав задачу с точностью до коэффициента O(logn). | Первый аппроксимационный алгоритм для задачи Sparsest Cut был разработан Лейтоном и Рао в 1988 году [13]. Применяя релаксацию линейного программирования для данной задачи, они получили аппроксимацию с коэффициентом O(log n), где n – размер входного графа. Впоследствии Арора, Рао и Вазирани [4] улучшили алгоритм Лейтона и Рао с помощью релаксации полуопределенного программирования, аппроксимировав задачу с точностью до коэффициента O(logn). | ||
Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу сбалансированного сепаратора. Разбиение (S;V n S) графа G называется c-сбалансированным сепаратором для 0 < c < j, если и S, и V n S имеют не менее cjVj вершин. Задача о сбалансированном разделителе состоит в том, чтобы найти сбалансированное c-разбиение с минимальной разреженностью. Эта разреженность обозначается как ac(G). | Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу сбалансированного сепаратора. Разбиение (S;V n S) графа G называется c-сбалансированным сепаратором для 0 < c < j, если и S, и V n S имеют не менее cjVj вершин. Задача о сбалансированном разделителе состоит в том, чтобы найти сбалансированное c-разбиение с минимальной разреженностью. Эта разреженность обозначается как ac(G). | ||
