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

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

Взамен этого факта можно попытаться эффективно вычислить линейный порядок <math>\pi \;</math> , для которого <math>bw_{\pi }(G) \le A \cdot bw(G)</math>, сделав при этом [[коэффициент аппроксимации]] A минимально возможным. Было показано, что задача получения любого значения A = O(1) является NP-полной [18]. Основная сложность при нахождении ширины ленты графа заключается в том, что целевая функция представляет собой максимум по всем ребрам графа. В силу этого подход «разделяй и властвуй» для нахождения ширины ленты графа неэффективен, в отличие от таких родственных задач, как алгоритм минимального линейного ранжирования [6] (здесь задача заключается в минимизации <math>\textstyle \sum_{ \{ u, v \} \in E} | \pi (u) - \pi (v) |</math>). Таким образом, требуется более глобальный алгоритм. Вначале следует обсудить нахождение хорошей нижней границы значения bw(G).

Фейге доказал следующие положения.

'''Теорема 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)/ аппроксимационный алгоритм для нахождения ширины ленты в графах общего вида.'''

Алгоритмическую структуру Фейге можно вкратце описать следующим образом.

1. Вычислить представление <math>f: \rightarrow \mathbb{R}^n</math> графа G в евклидовом пространстве.

2. Пусть <math>u_1, u_2, ..., u_n \; </math> – независимые случайные переменные N(0, 1); для каждой вершины <math>v \in V \; </math> вычислить <math>h(v) = \sum_{i=1}^n u_i f_i(v)</math>, где <math>f_i(v) \; </math> – i-я координата вектора <math>f(v) \;</math>.

N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1.

3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок.

 

Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора <math>a \in S^{n-1}</math> из (n-1)-мерной сферы <math>S^{n-1} \subset \mathbb{R}^n</math> и выдачи линейного порядка, порожденного значениями <math>h(v) = \big\langle a, f(v) \big\rangle </math>, где <math>\big\langle \cdot , \cdot \big\rangle </math> обозначает обычное скалярное произведение над <math>\mathbb{R}^n</math>. Иными словами, вначале алгоритм вычисляет отображение <math>f: \rightarrow \mathbb{R}^n</math>, проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции.

Как было отмечено ранее, задача нахождения ширины ленты графа находит применение в процессе предварительной обработки разреженных симметричных матриц. Минимизация ширины ленты матриц позволяет повысить эффективность определенных алгоритмов линейной алгебры – например, гауссова исключения; см. [3, 8, 17]. Последующие работы показали, что техники Фейге можно применять к задачам проектирования СБИС [19].

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