Аппроксимация метрических пространств древесными метриками: различия между версиями

Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой <math>O(log^2 \; n)</math> – это лучший результат по сравнению с exp(O(log nloglog n)) в [1]. Позднее Бартал [3], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [18], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [5], Факчаренфол, Рао и Талвар [9] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница привязана к константному коэффициенту.