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

Разработка алгоритма аппроксимации

Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задачи построения [[дерево Штейнера|дерева Штейнера]] в этих метрических пространствах носят названия [[Евклидова задача Штейнера|евклидовой задачи Штейнера]] (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-дерева Штейнера приводит к значительному различию при анализе этих двух типов деревьев. В чем заключается сложность такого анализа? Это будет описано ниже.

Если множество <math>\mathcal{F} \;</math> состоит из всех полных компонентов размером не более 3, этот жадный алгоритм дает на выходе 3-ограниченное дерево Штейнера, введенное Зеликовским [14]. Если <math>\mathcal{F} \;</math> состоит из всех трехлучевых звезд и всех ребер, где трехлучевая звезда представляет собой дерево с 3 листьями и центральной вершиной, то жадный алгоритм дает на выходе итеративное 1-дерево Штейнера. Интересный факт, на которой обратили внимание Ду и коллеги [9], заключается в том, что функция gain(<math>\cdot</math>) является субмодулярной над всеми полными компонентами размера не более 3, но не является субмодулярной над всеми трехлучевыми звездами и всеми ребрами.

Доказательство. Предположим, что f является субмодулярной. Положим <math>B = A \cup \{ x \} \;</math> и <math>C = A \cup \{ y \} \;</math>. Тогда <math>B \cup C = A \cup A \cup \{ x, y \} \;</math> и <math>B \cap C = A \;</math>. Следовательно, должно иметь место