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

Арора и др. предлагают <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>. Тогда существует алгоритм с полиномиальным временем выполнения для нахождения разбиения (S, V \ S), где <math>S \subset V, S \ne 0</math>, имеющего разреженность не более <math>O(\sqrt{log \; n} \alpha(G))</math>.'''

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