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

Показатели сложности аппроксимации для задачи о самом неплотном разрезе довольно слабы. Недавно Чужой и Ханна [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>-аппроксимаций для этих задач остаются нерешенными вопросами.

Ориентированная версия задачи Sparset Cut также изучалась, и для нее известна сложность аппроксимации с точностью до <math>2^{\Omega(log^{1 - \epsilon} n)}</math> [9]. С другой стороны, лучшая аппроксимация, известная для этой задачи, дает только полиномиальный коэффициент – а именно, <math>O(n^{11/23} log^{O(1)} n)</math>, полученный Аггарвалом, Алоном и Чарикаром [2].