Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
Еще одной важной задачей является задача [[лучшая аппроксимация|лучшей аппроксимации]]. Довольно долгое время не удавалось доказать наличие аппроксимации с коэффициентом эффективности меньше обратного значения отношения Штейнера. Первый прорыв совершил Зеликовский [14], который нашел 11/6-аппроксимацию с полиномиальным временем выполнения для задачи NST, что лучше 1/2 – обратного значения отношения Штейнера для сети с взвешенными ребрами. Позднее Берман и Рамайе [2] предложили 92/72-аппроксимацию с полиномиальным временем выполнения для RST, а Ду, Цзян и Фэн [8] закрыли тему, показав, что в любом метрическом пространстве существует аппроксимация с полиномиальным временем выполнения с коэффициентом эффективности меньше обратного значения отношения Штейнера, при условии, что для любого множества с фиксированным количеством точек его дерево Штейнера вычислимо за полиномиальное время. | Еще одной важной задачей является задача [[лучшая аппроксимация|лучшей аппроксимации]]. Довольно долгое время не удавалось доказать наличие аппроксимации с коэффициентом эффективности меньше обратного значения отношения Штейнера. Первый прорыв совершил Зеликовский [14], который нашел 11/6-аппроксимацию с полиномиальным временем выполнения для задачи NST, что лучше 1/2 – обратного значения отношения Штейнера для сети с взвешенными ребрами. Позднее Берман и Рамайе [2] предложили 92/72-аппроксимацию с полиномиальным временем выполнения для RST, а Ду, Цзян и Фэн [8] закрыли тему, показав, что в любом метрическом пространстве существует аппроксимация с полиномиальным временем выполнения с коэффициентом эффективности меньше обратного значения отношения Штейнера, при условии, что для любого множества с фиксированным количеством точек его минимальное дерево Штейнера вычислимо за полиномиальное время. | ||