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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 91: Строка 91:




Арора и др. [5] предложили алгоритм псевдоаппроксимации с коэффициентом O(log n) для нахождения сбалансированных сепараторов в случае однородных либо взвешенных потоков, основанный на полуопределенной релаксации. Для неоднородной версии лучшую границу O( log n log log n) демонстрирует алгоритм Ароры и др. [ ]. Хот и Вишной [18] показали, что для неоднородной версии задачи полуопределенная релаксация [ ] имеет разрыв целостности не менее (loglog n)ll6~s для любого (5 > 0 и, более того, согласно их гипотезе об уникальной игре, (псевдо)аппроксимация задачи о сбалансированном сепараторе с любым константным коэффициентом является NP-полной. Краутгамер и Рабани [20] усилили разрыв целостности в задаче полуопределенного программирования (SDP) до Q (log log n). Деванур и др. продемонстрировали разрыв целостности в размере £?(loglog n) для формулировки задачи SDP даже в однородном случае.
Арора и др. [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 даже в однородном случае.
 


== Реализация ==
== Реализация ==
4551

правка

Навигация