Ширина ленты графа: различия между версиями

[[Алгоритмы аппроксимации]]; [[метрические вложения]]

'''Теорема 1. Существует эффективный алгоритм, который для графа <math>G = (V, E) \; </math> устанавливает линейный порядок <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>, для которого <math>bw_{\pi } (G) \le O \Big( (log \; n)^3 \sqrt{log \; n \; log \; log \; n} \Big) \cdot D(G)</math>. В частности, имеется полилогарифмический относительно n /poly(log n)/ алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида.'''

Эта интересная гипотеза не доказана даже для специального случая, когда G является деревом (в [ ] приведены наилучшие результаты для деревьев). Наилучшая известная граница в общем случае, основанная на работах [7, 10], имеет вид <math>bw(G) = O(log \; n)^{3.5} \cdot D(G)</math>. Известно, что приведенная в гипотезе верхняя граница является наилучшей возможной, даже для деревьев [4]. Можно ожидать, что подобные комбинаторные исследования позволят усовершенствовать алгоритмы аппроксимации.

Однако наилучшие алгоритмы аппроксимации, достигающие показателя <math>O((log \; n)^3 (log \; log \; n)^{1/4)}</math>, не основываются на границе локальной плотности. Они скорее представляют собой гибрид подходов полуопределенного программирования [1, 5] с учетом предложений Фейге и методов вложения с учетом объема, изложенных в [12, 16]. Определение аппроксимируемости задачи нахождения ширины ленты графа является значимой открытой проблемой; для ее решения требуется улучшение как верхней, так и нижней границ.