Деревья Штейнера: различия между версиями

Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задача построения дерева Штейнера в этих метрических пространствах носит название евклидова дерева Штейнера (Euclidean Steiner Tree, EST), прямолинейного дерева Штейнера (Rectilinear Steiner Tree, RST) и сетевого дерева Штейнера (Network Steiner Tree, NST), соответственно. Было обнаружено, что для EST и RST имеются схемы аппроксимации с полиномиальным временем исполнения (PTAS) при помощи адаптивного разбиения. Однако для NST существует положительное число r, такое, что вычисление r-аппроксимации является NP-полной задачей. До настоящего момента лучший коэффициент эффективности для аппроксимации NST с полиномиальным временем выполнения был получен при помощи k-ограниченных деревьев Штейнера. Однако на практике очень часто используется итеративное 1-дерево Штейнера. Фактически итеративное 1-дерево Штейнера уже давно предлагалось в качестве кандидата на хорошую аппроксимацию минимальных деревьев Штейнера. Оно отлично проявило себя в компьютерных экспериментах, однако не было проведено корректного анализа, который показал бы, что коэффициент эффективности итеративного 1-дерева Штейнера превосходит коэффициент эффективности минимального остовного дерева. Недавно такую работу проделали Ду и коллеги [9]. Небольшое различие в построении 3-ограниченного дерева Штейнера и итеративного 1-дерева Штейнера приводит к значительному различию при анализе этих двух типов деревьев. В чем заключается сложность такого анализа? Это будет описано ниже.