Каков наилучший алгоритм вычисления прямолинейного минимального дерева Штейнера?

Существует множество алгоритмов, которые находят аппроксимации прямолинейных деревьев минимумов Штейнера (RSMT). Среди них:

  • набор алгоритмов, которые находят минимальные остовные деревья
  • РСТ-Т (прямолинейное одноствольное дерево Штейнера)
  • BGA (пакетный жадный алгоритм)
  • BI1S (пакетное повторяющееся дерево 1-Штейнера)
  • FLUTE (метод быстрой интерполяционной таблицы для построения RSMT и оценки длины проводов)

Было показано, что длина RSMT может в 3/2 раза превышать длину прямолинейного остовного минимального дерева. Я не нашел в литературе границ для других алгоритмов. Они существуют?

FLUTE кажется самым эффективным алгоритмом из всех, но я не знаю, что это наихудший случай и верхняя граница. Было ли оно найдено?

Есть ли у какого-либо алгоритма границы менее 3/2?


algorithm approximation computational-geometry
person Andrei Botalov    schedule 24.11.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Арора и Митчелл дал схемы аппроксимации с полиномиальным временем (= для всех эпсилон> 0, (1 + эпсилон)-аппроксимация ) для евклидова дерева Штейнера. Я считаю, что идеи могут быть непосредственно адаптированы к прямолинейному варианту.

person Per    schedule 25.11.2011
comment
Алгоритм имеет очень высокую вычислительную сложность - O(n^O(m)) - person Andrei Botalov; 12.12.2011
comment
Что м? Арора сократил время работы до O(f(epsilon) n polylog(n)). - person Per; 12.12.2011