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

Одним из примеров является задача о минимальном разрезе с линейным расположением. В этой задаче цель заключается в упорядочении вершин заданного n-вершинного графа G от 1 до и таким образом, чтобы минимизировать емкость наибольшего из разрезов ({1, 2, ..., i}, {i + 1, ..., n}), i <math>\in</math> [1, n]. При наличии p-аппроксимации задачи о сбалансированном разделителе, следующий алгоритм «разделяй и властвуй» дает <math>O(\rho \; log \; n)</math>-аппроксимацию задачи о минимальном разрезе с линейным упорядочением: следует найти сбалансированный сепаратор в графе, затем рекурсивно упорядочить две части и объединить эти упорядочения. Аппроксимация следует из того, что если в графе имеется сбалансированный сепаратор с расширением <math>\alpha_c(G)</math>, то на каждом уровне разрезается только <math>O(\rho n \alpha_n(G))</math> ребер, а учитывая, что сбалансированный сепаратор вычисляется на каждом шаге, количество уровней рекурсии составляет не более O(log n).

 

 

Задача о самом неплотном разрезе также тесно связана с проблемой вложения квадратично-евклидовой метрики в Манхэттенскую метрику (<math>\ell_1</math>) с малым искажением. В частности, разрыв целостности релаксации полуопределенного программирования Ароры и др. для задачи о разрезе (обобщенной на включение весов вершин и пропускной способности ребер) в точности равен наихудшему искажению для вложения квадратично-евклидовой метрики в манхэттенскую метрику. Используя технологию, представленную Аророй и коллегами, были получены улучшенные вложения квадратично-евклидовой метрики в манхэттенскую метрику [5, 7].