4501
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→История и предпосылки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Хорошо известной задачей является гипотеза Гилберта-Поллака об отношении Штейнера, представляющем собой минимальное отношение длин между минимальным деревом Штейнера и минимальным остовным деревом | Хорошо известной задачей является гипотеза Гилберта-Поллака об отношении Штейнера, представляющем собой минимальное отношение длин между минимальным деревом Штейнера и минимальным остовным деревом на том же множестве точек. Гилберт и Поллак в 1968 году предположили, что отношение Штейнера на евклидовой плоскости равно <math>\sqrt{3/2} \;</math> и достигается для трех вершин равностороннего треугольника. Доказательству этой гипотезы было посвящено множество работ, в конечном итоге ее доказали Ду и Хван [7]. | ||
| Строка 44: | Строка 44: | ||
Анализ итеративного 1-дерева Штейнера также долго время оставался нерешенной задачей. С тех пор как Чанг [4, 5] в 1972 году предположил, что итеративное 1-дерево Штейнера аппроксимирует минимальное дерево Штейнера, его эффективность в компьютерных экспериментах оказалась весьма высокой [10, 13], однако подкреплений со стороны теоретического анализа этому утверждению до сих пор не найдено. Фактически и k-ограниченное дерево Штейнера, и итеративное 1-дерево Штейнера строятся при помощи жадных алгоритмов, но с различными типами гармонических функций. В случае итеративного 1-дерева Штейнера гармоническая функция не является субмодулярной, тогда как в случае k-ограниченного дерева Штейнера она является таковой; свойство, выполняющееся для второго типа деревьев, может оказаться неверным для первого. Оказалось, что субмодулярность гармонической функции исключительно важна для анализа жадных аппроксимаций [11]. Ду и др. [9] дали точный анализ для итеративного 1-дерева Штейнера при помощи обобщенной техники обработки несубмодулярной гармонической функции. | Анализ итеративного 1-дерева Штейнера также долго время оставался нерешенной задачей. С тех пор как Чанг [4, 5] в 1972 году предположил, что итеративное 1-дерево Штейнера аппроксимирует минимальное дерево Штейнера, его эффективность в компьютерных экспериментах оказалась весьма высокой [10, 13], однако подкреплений со стороны теоретического анализа этому утверждению до сих пор не найдено. Фактически и k-ограниченное дерево Штейнера, и итеративное 1-дерево Штейнера строятся при помощи жадных алгоритмов, но с различными типами гармонических функций. В случае итеративного 1-дерева Штейнера гармоническая функция не является субмодулярной, тогда как в случае k-ограниченного дерева Штейнера она является таковой; свойство, выполняющееся для второго типа деревьев, может оказаться неверным для первого. Оказалось, что субмодулярность гармонической функции исключительно важна для анализа жадных аппроксимаций [11]. Ду и др. [9] дали точный анализ для итеративного 1-дерева Штейнера при помощи обобщенной техники обработки несубмодулярной гармонической функции. | ||
== Основные результаты == | == Основные результаты == | ||