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

После статьи Бартала в 1996 году было найдено множество применений алгоритмов аппроксимации. Многие из них позволяют решать задачи на древесных метриках или HST-метриках. Аппроксимируя метрики общего вида при помощи этих метрик, можно превратить их в алгоритмы для метрик общего вида, как правило, с потерей только члена O(log n) в коэффициенте аппроксимации. Среди примеров подобного подхода можно упомянуть разметку при помощи метрики, построение сетей с применением «оптового» подхода и группировку деревьев Штейнера. Среди новых областей применения стоит отметить алгоритм аппроксимации для Unique Games [12], проектирование информационных сетей [13] и сетей с рассеянной маршрутизацией [11].