Вычисление расстояния Громова—Хаусдорфа для метрических деревьев

Расстояние Громова—Хаусдорфа (GH) является естественным способом измерения расстояния между двумя метрическими пространствами. Мы доказываем, что аппроксимация расстояния GH для геодезических метрик на паре деревьев с коэффициентом, меньшим 3, является NP-трудной задачей. В дополнение к этому результату мы предлагаем полиномиальный алгоритм аппроксимации с коэффициентом O(min(n, √(rn))) для вычисления расстояния GH между парой метрических деревьев, где r — отношение длины самого длинного ребра в обоих деревьях к длине самого короткого ребра. Для метрических деревьев с рёбрами единичной длины это даёт алгоритм аппроксимации с коэффициентом O(√n).