Самый неплотный разрез: различия между версиями

Задача о самом неплотном разрезе состоит в том, чтобы найти подмножество <math>S \subset V</math> с минимальной разреженностью и определить разреженность графа.

Первый аппроксимационный алгоритм для задачи 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).