4817
правок
Самый неплотный разрез: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Основные результаты == | == Основные результаты == | ||
Арора и др. предлагают O( | Арора и др. предлагают <math>O(\sqrt{log \; n})</math>-''псевдоаппроксимацию'' задачи о сбалансированном сепараторе с помощью полуопределенного программирования. В частности, для константы c 2 (0, j] они получили сепаратор с балансом c0, что несколько хуже c (то есть c0 < c), но с разреженностью в пределах O(logn) от разреженности оптимального c-сбалансированного сепаратора. | ||