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

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


== Постановка задачи ==
Рассмотрим взвешенный связный мультиграф <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> определяется следующим образом:


<math>stretch_T(u, v) = \frac{dist_T(u, v)}{dist_G(u, v)}
</math>


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


<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]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений.

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


<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>

== Применение ==
Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [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>.


Применяя остовные деревья с низким растяжением, предложенные в [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], для построения вложений с константным средним растяжением, где среднее значение берется по всем ''парам вершин'', а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.

== Открытые вопросы ==
Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей <math>O(log^2 n \; log \; log \; n)</math> и нижней границей <math>\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)