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

Чарикар, Чекури, Гель, Гуха и Плоткин [6] показали, как найти распределение O(n log n) древесных метрик, <math>\alpha \;</math>-вероятностно аппроксимирующее заданную метрику, при условии возможности решения двойственной задачи. Алгоритм теоремы 1 может быть дерандомизирован при помощи метода с использованием условного матожидания, что дает в результате требуемую древесную метрику <math>\alpha = O(log \; n)</math>. Еще один алгоритм, основанный на модификации техники наращивания областей, был представлен в [9] и независимо от этого – в работе Бартала.