4551
правка
Сепараторы в графах: различия между версиями
Материал из WEGA
→Родственные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
Арора и др. [5] предложили алгоритм псевдоаппроксимации с коэффициентом O(log n) для нахождения сбалансированных сепараторов в случае однородных либо взвешенных потоков, основанный на полуопределенной релаксации. Для неоднородной версии лучшую границу O( log n log log n) демонстрирует алгоритм Ароры и др. [ ]. Хот и Вишной [18] показали, что для неоднородной версии задачи полуопределенная релаксация [ ] имеет разрыв целостности не менее ( | Арора и др. [5] предложили алгоритм псевдоаппроксимации с коэффициентом <math>O(\sqrt {log \; n})</math> для нахождения сбалансированных сепараторов в случае однородных либо взвешенных потоков, основанный на полуопределенной релаксации. Для неоднородной версии лучшую границу O( log n log log n) демонстрирует алгоритм Ароры и др. [4]. Хот и Вишной [18] показали, что для неоднородной версии задачи полуопределенная релаксация [5] имеет разрыв целостности не менее <math>(log \; log \; n)^{1/6 - \delta}</math> для любого <math>\delta > 0 \;</math> и, более того, согласно их гипотезе об уникальной игре, (псевдо)аппроксимация задачи о сбалансированном сепараторе с любым константным коэффициентом является NP-полной. Краутгамер и Рабани [20] усилили разрыв целостности в задаче полуопределенного программирования (SDP) до <math>\Omega (log \; log \; n)</math>. Деванур и др. продемонстрировали разрыв целостности в размере <math>\Omega (log \; log \; n)</math> для формулировки задачи SDP даже в однородном случае. | ||
== Реализация == | == Реализация == | ||
