Остовные деревья с низким растяжением: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 14 промежуточных версий 1 участника)
Строка 4: Строка 4:


== Постановка задачи ==
== Постановка задачи ==
Рассмотрим взвешенный связный мультиграф G = (V, E, omega), где omega – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин u, v 2 V за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G растяжение дуги (u, v) 2 E определяется следующим образом:
Рассмотрим взвешенный связный мультиграф <math>G = (V, E, \omega ) \; </math>, где <math>\omega \;</math> – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин <math>u, v \in V \;</math> за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G [[растяжение]] дуги <math>(u, v) \in E \;</math> определяется следующим образом:


distT(u;v)
stretchT(u, v) = ——( u ; v distG(u, v)
and the average stretch over all edges of E is
stretchT(u, v) :
avestr(G; T) = 1
\E\
(u;v)2E
1    '


Среднее растяжение мультиграфа G = (v, E, omega) определяется как наименьшее среднее растяжение остовного дерева tree T графа G – avestr(G; T). Среднее растяжение целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n).
<math>stretch_T(u, v) = \frac{dist_T(u, v)}{dist_G(u, v)}
</math>




Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что
а среднее растяжение по всем дугам E составляет
expstr(G;D) =    max  ET2D(stretchT(u;v))
e=(u;v)2E


насколько возможно мало. Аналогично, expstr(G) = minD fexpstr(G; D)g, где минимум берется среди всех распределений D остовных деревьев графа G, и expstr(n) = maxGfexpstr(G)g, где максимум берется среди всех n-вершинных мультиграфов.
 
<math>avestr(G, T) = \frac{1}{|E|} \sum_{(u, v) \in E} stretch_T(u, v).</math>
 
 
 
Среднее растяжение мультиграфа <math>G = (V, E, \omega ) \; </math> определяется как наименьшее среднее растяжение остовного дерева T графа G, обозначаемое avestr(G, T). Среднее растяжение для целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n).
 
 
Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что значение
 
 
<math>expstr(G, D) = max_{e = (u, v) \in E} \mathbf{E}_{T \in D} (stretch_T(u, v))</math>
 
 
насколько возможно мало. Аналогично, <math>expstr(G) = min_D \{ expstr(G, D) \} \;</math>, где минимум берется среди всех распределений D остовных деревьев графа G, и <math>expstr(n) = max_G \{ expstr(G) \} \; </math>, где максимум берется среди всех n-вершинных мультиграфов.




Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений.
Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений.


== Основные результаты ==
== Основные результаты ==
Эта задача изучалась еще в шестидесятых [8, 13, 15, 16]. Серьезный прогресс был достигнут Алоном и коллегами [2], показавшими, что
Эта задача изучалась еще в шестидесятых [8, 13, 15, 16]. Серьезный прогресс был достигнут Алоном и коллегами [2], показавшими, что
J2(log n) = avestr(n) = expstr(n)
= exp(O(plog n ■ log log n)) :


Элкин и коллеги [9] улучшили верхнюю границу и показали, что avestr(n) = expstr(n) = O(log2 n • loglog n) :


<math>\Omega(log \; n) = avestr(n) = expstr(n) = exp(O( \sqrt{log \; n \cdot log \; log \; n)}).</math>
Элкин и коллеги [9] улучшили верхнюю границу и показали, что <math>avestr(n) = expstr(n) = O(log^2 n \cdot log \; log \; n).</math>


== Применение ==
== Применение ==
Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [ ] первыми открыли удивительную связь между этими, на первый взгляд, совершенно разными задачами. Они применили остовные деревья из работы [ ] для разработки алгоритмов решения задач с временем исполнения m3/22O(l°g«bglog")iog(1/6). Шпильман и Тенг [14] улучшили их результат, продемонстрировав использование остовных деревьев [2] для решения систем линейных уравнений с диагональным преобладанием за время
Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [5] первыми открыли удивительную связь между этими, на первый взгляд, совершенно разными задачами. Они применили остовные деревья из работы [2] для разработки алгоритмов решения задач с временем выполнения <math>m^{3/2} 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) </math>. Шпильман и Тенг [14] улучшили их результат, продемонстрировав использование остовных деревьев [2] для решения систем линейных уравнений с диагональным преобладанием за время <math>m 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) </math>.
g » bglog n)




Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до mlogo(1)nlog(l/6) и до O(n(log nloglog n)2 log(l/e)) в случае, если системы планарны. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [ ], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем исполнения O(n(logn loglog n)2log(l/e)).
Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до <math>m log^{O(1)} n log(1 / \epsilon) \;</math>, а в случае, если системы планарны – до <math>O( n(log \; n \; log \; log \; n ) log (1 / \epsilon)) </math>. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [6], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем выполнения <math>O(n(log \; n \; log \; log \; n)^2 log(l / \epsilon))</math>.




Недавно Чекури и коллеги [ ] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.
Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.
В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [ ], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.


В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем ''парам вершин'', а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.


== Открытые вопросы ==
== Открытые вопросы ==
Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей O(log2 n log log n) и нижней границей Q(log n) значения avestr(n). Еще одна интересная тема – изучение остовных деревьев с низким растяжением для различных ограниченных семейств графов. В этом направлении недавно достигли заметного прогресса Эмек и Пелег [ ], построившие остовные деревья с низким растяжением со средним значением растяжения O(log n) для невзвешенных серийно-параллельных графов. Также обширным полем для исследований является нахождение других способов применения остовных деревьев с низким растяжением.
Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей <math>O(log^2 n \; log \; log \; n)</math> и нижней границей <math>\Omega(log \; n)</math> значения avestr(n). Еще одна интересная тема – изучение остовных деревьев с низким растяжением для различных ограниченных семейств графов. В этом направлении недавно достигли заметного прогресса Эмек и Пелег [11], построившие остовные деревья с низким растяжением со средним значением растяжения O(log n) для невзвешенных серийно-параллельных графов. Также обширным полем для исследований является нахождение других способов применения остовных деревьев с низким растяжением.




Наконец, имеется довольно близкое ослабленное понятие деревьев Штейнера или Бартала с низким растяжением. В отличие от остовных деревьев, дерево Штейнера не обязано быть подграфом исходного графа; оно может содержать ребра и вершины, не входящие в состав исходного графа. Однако при этом требуется, чтобы расстояния в дереве Штейнера были не меньше расстояний в исходном графе. Деревья Штейнера с низким растяжением широко исследовались [3, 4, 12]. Факхаренфол и коллеги [ ] разработали алгоритм построения деревьев Штейнера с низким растяжением со средним значением растяжения O(log n). В настоящее время неизвестно, будет ли техника, используемая при изучении деревьев Штейнера с низким растяжением, полезна при улучшении границ остовных деревьев с низким растяжением.
Наконец, имеется довольно близкое ослабленное понятие [[дерево Штейнера|деревьев Штейнера]] или [[дерево Бартала|Бартала]] с низким растяжением. В отличие от остовных деревьев, дерево Штейнера не обязано быть подграфом исходного графа; оно может содержать ребра и вершины, не входящие в состав исходного графа. Однако при этом требуется, чтобы расстояния в дереве Штейнера были не меньше расстояний в исходном графе. Деревья Штейнера с низким растяжением широко исследовались [3, 4, 12]. Факхаренфол и коллеги [12] разработали алгоритм построения деревьев Штейнера с низким растяжением со средним значением растяжения O(log n). В настоящее время неизвестно, будет ли техника, используемая при изучении деревьев Штейнера с низким растяжением, полезна при улучшении границ остовных деревьев с низким растяжением.
 


== См. также ==
== См. также ==
Строка 91: Строка 92:


16. Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969). (In Russian)
16. Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969). (In Russian)
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 11:31, 22 ноября 2024

Ключевые слова и синонимы

Остовные деревья с низким средним коэффициентом растяжения


Постановка задачи

Рассмотрим взвешенный связный мультиграф [math]\displaystyle{ G = (V, E, \omega ) \; }[/math], где [math]\displaystyle{ \omega \; }[/math] – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин [math]\displaystyle{ u, v \in V \; }[/math] за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G растяжение дуги [math]\displaystyle{ (u, v) \in E \; }[/math] определяется следующим образом:


[math]\displaystyle{ stretch_T(u, v) = \frac{dist_T(u, v)}{dist_G(u, v)} }[/math]


а среднее растяжение по всем дугам E составляет


[math]\displaystyle{ avestr(G, T) = \frac{1}{|E|} \sum_{(u, v) \in E} stretch_T(u, v). }[/math]


Среднее растяжение мультиграфа [math]\displaystyle{ G = (V, E, \omega ) \; }[/math] определяется как наименьшее среднее растяжение остовного дерева T графа G, обозначаемое avestr(G, T). Среднее растяжение для целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n).


Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что значение


[math]\displaystyle{ expstr(G, D) = max_{e = (u, v) \in E} \mathbf{E}_{T \in D} (stretch_T(u, v)) }[/math]


насколько возможно мало. Аналогично, [math]\displaystyle{ expstr(G) = min_D \{ expstr(G, D) \} \; }[/math], где минимум берется среди всех распределений D остовных деревьев графа G, и [math]\displaystyle{ expstr(n) = max_G \{ expstr(G) \} \; }[/math], где максимум берется среди всех n-вершинных мультиграфов.


Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений.

Основные результаты

Эта задача изучалась еще в шестидесятых [8, 13, 15, 16]. Серьезный прогресс был достигнут Алоном и коллегами [2], показавшими, что


[math]\displaystyle{ \Omega(log \; n) = avestr(n) = expstr(n) = exp(O( \sqrt{log \; n \cdot log \; log \; n)}). }[/math]

Элкин и коллеги [9] улучшили верхнюю границу и показали, что [math]\displaystyle{ avestr(n) = expstr(n) = O(log^2 n \cdot log \; log \; n). }[/math]

Применение

Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [5] первыми открыли удивительную связь между этими, на первый взгляд, совершенно разными задачами. Они применили остовные деревья из работы [2] для разработки алгоритмов решения задач с временем выполнения [math]\displaystyle{ m^{3/2} 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) }[/math]. Шпильман и Тенг [14] улучшили их результат, продемонстрировав использование остовных деревьев [2] для решения систем линейных уравнений с диагональным преобладанием за время [math]\displaystyle{ m 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) }[/math].


Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до [math]\displaystyle{ m log^{O(1)} n log(1 / \epsilon) \; }[/math], а в случае, если системы планарны – до [math]\displaystyle{ O( n(log \; n \; log \; log \; n ) log (1 / \epsilon)) }[/math]. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [6], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем выполнения [math]\displaystyle{ O(n(log \; n \; log \; log \; n)^2 log(l / \epsilon)) }[/math].


Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.

В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.

Открытые вопросы

Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math] и нижней границей [math]\displaystyle{ \Omega(log \; n) }[/math] значения avestr(n). Еще одна интересная тема – изучение остовных деревьев с низким растяжением для различных ограниченных семейств графов. В этом направлении недавно достигли заметного прогресса Эмек и Пелег [11], построившие остовные деревья с низким растяжением со средним значением растяжения O(log n) для невзвешенных серийно-параллельных графов. Также обширным полем для исследований является нахождение других способов применения остовных деревьев с низким растяжением.


Наконец, имеется довольно близкое ослабленное понятие деревьев Штейнера или Бартала с низким растяжением. В отличие от остовных деревьев, дерево Штейнера не обязано быть подграфом исходного графа; оно может содержать ребра и вершины, не входящие в состав исходного графа. Однако при этом требуется, чтобы расстояния в дереве Штейнера были не меньше расстояний в исходном графе. Деревья Штейнера с низким растяжением широко исследовались [3, 4, 12]. Факхаренфол и коллеги [12] разработали алгоритм построения деревьев Штейнера с низким растяжением со средним значением растяжения O(log n). В настоящее время неизвестно, будет ли техника, используемая при изучении деревьев Штейнера с низким растяжением, полезна при улучшении границ остовных деревьев с низким растяжением.

См. также

Литература

1. Abraham, I., Bartal, Y., Neiman, O.: Embedding Metrics into Ul-trametrics and Graphs into Spanning Trees with Constant Average Distortion. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, January 2007

2. Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic gane and its application to the k-server problem. SIAM J. Comput. 24(1), 78-100 (1995). Also available Technical Report TR-91-066, ICSI, Berkeley (1991)

3. Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Berlington, Oct. 1996 pp. 184-193

4. Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the 30th annual ACM symposium on Theory of computing, Dallas, 23-26 May 1998, pp. 161-168

5. Boman, E., Hendrickson, B.: On spanning tree preconditioners. Manuscript, Sandia National Lab. (2001)

6. Boman, E., Hendrickson, B., Vavasis, S.: Solving elliptic finite element systems in near-linear time with suppost preconditioners. Manuscript, Sandia National Lab. and Cornell, http://arXiv.org/abs/cs/0407022 Accessed 9 July 2004

7. Chekuri, C., Hagiahayi, M.T., Kortsarz, G., Salavatipour, M.: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. In: Proceedings of the 47th Annual Symp. on Foundations of Computer Science, Berkeley, Oct. 2006, pp. 677-686

8. Deo, N., Prabhu, G.M., Krishnamoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw. 8, 26^2(1982)

9. Elkin, M., Emek, Y., Spielman, D., Teng, S.-H.: Lower-Stretch Spanning Trees. In: Proc. of the 37th Annual ACM Symp. On Theory of Computing, STOC'05, Baltimore, May 2005, pp. 494-503

10. Elkin, M., Liebchen, C., Rizzi, R.: New Length Bounds for Cycle Bases. Inf. Proc. Lett. 104(5), 186-193 (2007)

11. Emek, Y., Peleg, D.: A tight upper bound on the probabilistic embedding of series-parallel graphs. In: Proc. of Symp. on Discr. Algorithms, SODA'06, Miami, Jan. 2006, pp. 1045-1053

12. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th annual ACM symposium on Theory of Computing, San Diego, June 2003, pp. 448^55

13. Horton, J.D.: A Polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2), 358-366 (1987)

14. Spielman, D., Teng, S.-H.: Nearly-linear time algorithm for graph partitioning, graph sparsification, and solving linear systems. In: Proc. of the 36th Annual ACM Symp. on Theory of Computing, STOC'04, Chicago. USA, June 2004, pp. 81-90

15. Stepanec, G.F.: Basis systems of vector cycles with extremal properties in graphs. Uspekhi Mat. Nauk 19, 171-175 (1964). (In Russian)

16. Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969). (In Russian)