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

Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу о сбалансированном сепараторе. Разбиение <math>(S, V \backslash S)</math> графа G называется c-сбалансированным сепаратором для <math>0 < c \le \frac{1}{2}</math>, если и <math>S</math> и <math>V \backslash S</math> имеют не менее c|V| вершин. Целью задачи о сбалансированном сепараторе является поиск c-сбалансированного разбиения с минимальной разреженностью, которая обозначается как <math>\alpha_c(G)</math>.

Арора и др. предлагают <math>O(\sqrt{log \; n})</math>-''псевдоаппроксимацию'' задачи о сбалансированном сепараторе с помощью полуопределенного программирования. В частности, для константы <math>c \in (0, \frac{1}{2}]</math> они получили сепаратор с балансом c', который несколько хуже c (то есть c' < c), но с разреженностью в пределах <math>O(\sqrt{log \; n})</math> от разреженности оптимального c-сбалансированного сепаратора.

'''Теорема 1. Пусть имеется граф G = (V, E) и пусть <math>\alpha_c(G)</math> – минимальное реберное расширение c-сбалансированного сепаратора в этом графе. Тогда для любой фиксированной константы a < 1 существует алгоритм с полиномиальным временем выполнения для нахождения c'-сбалансированного сепаратора в G, где c' <math>\ge</math> ac, имеющий реберное расширение не более <math>O(\sqrt{log \; n } \; \alpha_c(G))</math>.'''

'''Теорема 2. Пусть G = (V, E) – граф с разреженностью <math>\alpha(G)</math>. Тогда существует алгоритм с полиномиальным временем выполнения для нахождения разбиения <math>(S, V \backslash S)</math>, где <math>S \subset V, S \ne 0</math>, имеющего разреженность не более <math>O(\sqrt{log \; n} \; \alpha(G))</math>.'''

Неформально результат гласит, что если набор точек в n-мерном пространстве случайным образом проецируется на прямую, то хороший сепаратор на прямой с высокой вероятностью является хорошим сепаратором (в смысле квадратичного евклидова расстояния) в исходном пространстве высокой размерности. Разделение на прямой связано с разделением в исходном пространстве посредством следующего определения растяжения.

'''Определение 1''' (Опр. 4 в [4]). Пусть <math>\vec x_1, \vec x_2, ..., \vec x_n</math> – множество из n точек в пространстве <math>\mathcal{R}^n</math>, снабженном квадратично-евклидовой метрикой <math>d(x, y) = \parallel x - y \parallel_2^2</math>. Множество точек считается ''<math>(t, \gamma, \beta)</math>-растяженным в масштабе <math>\ell</math>'', если для хотя бы части <math>\gamma</math> всех n-мерных единичных векторов ''u'' существует частичное соответствие <math>M_u = \{ (x_i, y_i) \} _i</math> между этими точками, причем <math>|M_u| \ge \beta n</math>, такое, что для всех <math>(x, y) \in M_u, d(x, y) \le \ell^2</math> и <math>\langle u, \vec x - \vec y \rangle \ge t \ell / \sqrt{n}</math>. Здесь <math>\langle \cdot , \cdot \rangle</math> обозначает скалярное произведение двух векторов.

'''Теорема 3. Для любых <math>\gamma, \beta > 0</math> существует константа <math>C = 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 до n таким образом, чтобы минимизировать пропускную способность наибольшего из разрезов ({1, 2, ..., i}, {i + 1, ..., n}), i <math>\in</math> [1, n]. При наличии <math>\rho</math>-аппроксимации задачи о сбалансированном сепараторе следующий алгоритм «разделяй и властвуй» дает <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].

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