4817
правок
Самый неплотный разрез: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Основные результаты == | == Основные результаты == | ||
Арора и др. предлагают <math>O(\sqrt{log \; n})</math>-''псевдоаппроксимацию'' задачи о сбалансированном сепараторе с помощью полуопределенного программирования. В частности, для константы c | Арора и др. предлагают <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. Пусть | '''Теорема 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>.''' | ||
| Строка 34: | Строка 34: | ||
Теорема 2. Пусть G = (V, E) – граф с | '''Теорема 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>.''' | ||