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

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

Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение D над O(nlogn) древесных метрик, которая O(log n)-вероятностно аппроксимирует (V, d).

Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта Gupta [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент.