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

Анализ итеративного 1-дерева Штейнера также долго время оставался нерешенной задачей. С тех пор как Чанг [4, 5] в 1972 году предположил, что итеративное 1-дерево Штейнера аппроксимирует минимальное дерево Штейнера, его эффективность в компьютерных экспериментах оказалась весьма высокой [10, 13], однако подкреплений со стороны теоретического анализа этому утверждению до сих пор не найдено. Фактически и k-ограниченное дерево Штейнера, и итеративное 1-дерево Штейнера строятся при помощи жадных алгоритмов, но с различными типами гармонических функций. В случае итеративного 1-дерева Штейнера гармоническая функция не является субмодулярной, тогда как в случае k-ограниченного дерева Штейнера она является таковой; свойство, выполняющееся для второго типа деревьев, может оказаться неверным для первого. Оказалось, что субмодулярность гармонической функции исключительно важна для анализа жадных аппроксимаций [11]. Ду и др. [9] дали точный анализ для итеративного 1-дерева Штейнера при помощи обобщенной техники обработки несубмодулярной гармонической функции.

== Основные результаты ==

Рисунок 2.

== Применение ==

Задача построения дерева Штейнера является классической NP-полной проблемой и имеет множество приложений при разработке компьютерных микросхем, междугородних телефонных линий, многоадресной маршрутизации в сетях телекоммуникаций и т.п. Разработано множество эвристик жадного типа для построения деревьев Штейнера. Большинство из них демонстрируют высокую эффективность в компьютерных экспериментах, однако без подкрепления со стороны теоретического анализа. Предложенный подход может стать его основой.

== Открытые вопросы ==