1294
правки
Ширина ленты графа: различия между версиями
Материал из WEGA
→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 10 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
[[ | [[Аппроксимационные алгоритмы]]; [[метрические вложения]] | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 13: | Строка 13: | ||
Локальная плотность | Локальная плотность | ||
Обозначим для любой пары вершин <math>u, v \in V \;</math> за <math>d(u,v) \;</math> кратчайшее расстояние между u и v в графе G. Затем определим <math>B(v, r) = \{ u \in V : d(u, v) \le r \}</math> как шар радиуса r вокруг вершины <math>v \in V \;</math>. Наконец, определим локальную плотность G как <math>D(G) = max_{v \in V, r \ge 1} | B(v, r) | / (2r)</math>. Нетрудно заметить, что <math>bw(G) \ge D(G) \;</math>. Было высказано предположение, что существует верхняя граница вида <math>bw(G) \le poly(log \; n) \cdot D(G)</math>, но до выхода основополагающей работы | Обозначим для любой пары вершин <math>u, v \in V \;</math> за <math>d(u,v) \;</math> кратчайшее расстояние между u и v в графе G. Затем определим <math>B(v, r) = \{ u \in V : d(u, v) \le r \}</math> как шар радиуса r вокруг вершины <math>v \in V \;</math>. Наконец, определим локальную плотность G как <math>D(G) = max_{v \in V, r \ge 1} | B(v, r) | / (2r)</math>. Нетрудно заметить, что <math>bw(G) \ge D(G) \;</math>. Было высказано предположение, что существует верхняя граница вида <math>bw(G) \le poly(log \; n) \cdot D(G)</math>, но до выхода основополагающей работы Фейге [7] оно оставалось недоказанным. | ||
== Основные результаты == | == Основные результаты == | ||
Фейге доказал следующие положения. | |||
'''Теорема 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 в евклидовом пространстве. | |||
3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок. Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора a | 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) представляет собой стандартный способ реализации подобной случайной проекции. | |||
Вложения с учетом объема | Вложения с учетом объема | ||
Осталось охарактеризовать только этап (1). Функция f должна каким-либо образом сохранять структуру графа G, чтобы алгоритм мог выдавать порядок с низкой шириной ленты. Существование такой функции f обуславливается наличием поля метрических вложений с малым уровнем искажений (см., например, [2, 14]). Фейге предложил обобщение вложений с малым уровнем искажений до отображений, называемых вложениями с учетом объема. Грубо говоря, отображение f должно быть нерасширяющимся в том смысле, что <math>\parallel f(u) — f(v) \parallel \le 1</math> для каждого ребра <math>\{ u, v \} \in E \;</math>, и должно обладать следующим свойством: для любого набора из k вершин <math>v_1, ..., v_k \;</math>, <math>(k-1) \;</math>-мерный объем выпуклой оболочки точек <math>f(v_1), ..., f(v_k) \;</math> должен быть максимально возможно большим. Для оптимизации эффективности алгоритма выбирается подходящее значение k. Точные определения вложений с учетом объема и детальное изложение их построения можно найти в работах [7, 10, 11]. Файге показал, что модификация алгоритма вложения Бургейна [2] дает отображение <math>f: \rightarrow \mathbb{R}^n</math>, достаточно хорошее для обеспечения справедливости теоремы 1. | |||
Требование | |||
Требование <math>\parallel f(u) — f(v) \parallel \le 1</math> для каждого ребра {u, v} является естественным, поскольку f(u) и f(v) должны иметь сходные проекции на произвольное направление a; из этого интуитивно следует, что u и v будут отображаться в порожденном линейном порядке не слишком далеко друг от друга. Но даже если |h(u) — h(v)| мало, может оказаться, что между h(u) и h(v) проецируется слишком много вершин, из-за чего между u и v возникает значительное растяжение. Чтобы избежать такой ситуации, изображения вершин должны быть в достаточной мере «разнесены», что соответствует требованию большого объема выпуклой оболочки изображений. | |||
== Применение == | == Применение == | ||
Как было отмечено ранее, задача нахождения ширины ленты графа находит применение в процессе предварительной обработки разреженных симметричных матриц. Минимизация ширины ленты матриц позволяет повысить эффективность определенных алгоритмов линейной алгебры – например, гауссова исключения; см. [3, 8, 17]. Последующие работы показали, что техники | Как было отмечено ранее, задача нахождения ширины ленты графа находит применение в процессе предварительной обработки разреженных симметричных матриц. Минимизация ширины ленты матриц позволяет повысить эффективность определенных алгоритмов линейной алгебры – например, гауссова исключения; см. [3, 8, 17]. Последующие работы показали, что техники Фейге можно применять к задачам проектирования СБИС [19]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Вначале сформулируем гипотезу о ширине ленты (подробнее, например, в [13]). | Вначале сформулируем гипотезу о ширине ленты (подробнее, например, в [13]). | ||
'''Гипотеза: для любого графа G = (V, E) с n вершинами имеем <math>bw(G) = O(log \; n) \cdot D(G) \;</math>.''' | |||
Эта интересная гипотеза не доказана даже для специального случая, когда 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]. Определение аппроксимируемости задачи нахождения ширины ленты графа является значимой открытой проблемой; для ее решения требуется улучшение как верхней, так и нижней границ. | |||
== Литература == | == Литература == | ||
| Строка 89: | Строка 93: | ||
19. Vempala, S.: Random projection: A new approach to VLSI layout. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8-11 Oct 1998, pp. 389-398. | 19. Vempala, S.: Random projection: A new approach to VLSI layout. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8-11 Oct 1998, pp. 389-398. | ||
[[Категория: Совместное определение связанных терминов]] | |||
