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

Задача поиска распределения древесных метрик, вероятностно аппроксимирующее заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер <math>c_{uv} \;</math>; необходимо найти древесную метрику <math>d_T \;</math>, такую, что для всех <math>u, v \in Vd_T \;</math> верно <math>(u, v) \ge d(u, v) \;</math> и <math>\sum_{u, v \in V}  c_{uv} \cdot d_T(u, v) \le \alpha \sum_{u, v \in V} c_{uv} \cdot d(u, v) \;</math>.