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

'''Теорема 3. Для любых <math>\gamma, \beta ></math> 0 существует константа <math>С = C(\gamma, \beta)</math>, такая, что если <math>t > C \; log^{1/3} n</math>, то никакое множество из n точек в пространстве <math>\mathcal{R}^n</math> не может быть <math>(t, \gamma, \beta)</math>-растяженным для любого масштаба <math>\ell</math>.'''

Одним из примеров является задача о минимальном разрезе с линейным расположением. В этой задаче цель заключается в упорядочении вершин заданного 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).

Показатели сложности аппроксимации для задачи о самом неплотном разрезе довольно слабы. Недавно Чужой и Ханна [9] показали, что эта задача является APX-сложной, то есть существует константа <math>\epsilon > 0</math>, такая, что <math>(1 + \epsilon)</math>-аппроксимационный алгоритм для нее будет означать равенство P=NP. Предполагается, что взвешенная версия задачи NP-сложна для аппроксимации с коэффициентом, лучшим, чем <math>O((log \; log \; n)^c)</math> для некоторой постоянной ''c'', но известно, что это верно только в предположении версии так называемой гипотезы об уникальной игре [8, 12]. С другой стороны, известно, что релаксация полуопределенного программирования Ароры и др. имеет разрыв целостности <math>\Omega (log \; log \; n)</math> даже в невзвешенном случае [10]. Доказательство безусловной суперконстантной сложности для взвешенного или невзвешенного варианта задачи о самом неплотном разрезе, а также получение <math>o(\sqrt{log \; n})</math>-аппроксимаций для этих задач остаются нерешенными вопросами.