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