4551
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Перейти к навигации
Перейти к поиску
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 11:32, 1 ноября 2016
, 1 ноября 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл | Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл <math>C_n \;</math> с n вершинами, то любая древесная метрика, аппроксимирующая эту графовую метрику, имеет невязку <math>\Omega (n) \;</math> [17]. Однако Карп [15] заметил, что случайное остовное дерево <math>C_n \;</math> довольно неплохо аппроксимирует расстояния между двумя вершинами в <math>C_n \;</math>. Позднее Алон, Карп, Пелег и Уэст [1] доказали, что граница средней невязки при аппроксимации любой графовой метрики ее остовным деревом составляет <math>exp(O(\sqrt{log \; n \; log \; log \; n }))</math>. | ||