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

Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем.

Статья в SIGACT News [ ] представляет обзор метрической аппроксимации при помощи древесных метрик и более детальное обсуждение построения алгоритмов и техник. См. другие примеры применения в [3, 9].