Аппроксимация минимальной полосы пропускания на бинарных деревьях

14

Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами.

Решение проблемы является NP-полным даже для бинарных деревьев. Результаты сложности для минимизации пропускной способности. Гэри, Грэм, Джонсон и Кнут, SIAM J. Appl. Math., Vol. 34, № 3, 1978 .

Каков наиболее известный результат эффективной аппроксимируемости для вычисления минимальной полосы пропускания на двоичных деревьях? Какова наиболее известная условная твердость результата аппроксимации?

Мухаммед Аль-Туркистани
источник

Ответы:

7

Blache et. al. Об аппроксимационной неразрешимости проблемы пропускной способности, 1997 г. подтверждается, что для этой задачи не существует PTAS, если только , даже для (двоичных) деревьев. Унгер В. Сложность аппроксимации проблемы ширины полосы, 1998, показывает, что для любой константы k N не существует алгоритма аппроксимации полиномиального времени с коэффициентом аппроксимации k . Так что, к сожалению, нетпзнак равноNPКNК проблем с PTAS или APX .

Однако для некоторых типов графиков задача может быть решена или аппроксимирована за полиномиальное время. Для недавнего обзора см. Petit J., Дополнения к Обзору проблем макета, 2011 . В обзоре см. Таблицы 3, 4 и 8. Опрос также дает хороший список ссылок, если вы хотите углубиться в какое-то направление. Это более обновленная версия более раннего опроса, проведенного Диазом и др., Опрос о проблемах макета графика, 2002 .

О(4,83N)

Юхо
источник