Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstant-Time Dynamic Weight Approximation for Minimum Spanning Forest
124
0
0.0
(
0
)
Added by
Pan Peng
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give two fully dynamic algorithms that maintain a $(1+varepsilon)$-approximation of the weight $M$ of the minimum spanning forest of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 log W}/{varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes $Omega(log n)$ time per operation to maintain the exact weight of the MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+varepsilon)$-approximate weight of the MSF requires super constant time per operation, if $Wgeq (log n)^{omega_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(frac{1}{varepsilon^4}log^3(frac{1}{varepsilon}))$ update time if $W$ is not too large, more specifically, if $W= O({(m^*)^{1/6}}/{log n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement this result by showing that for any constant $varepsilon,alpha>0$ and $W=n^{alpha}$, any (randomized) data structure that dynamically maintains the weight of the MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Omega(varepsilon m^*)$ within a multiplicative factor of $(1+varepsilon)$ takes $Omega(log n)$ time per operation.
rate research
Read More
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with $n$ vertices and $m$ edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(sqrt n)$ processors and $O(log n)$ worst-case update time, for a total of $O(sqrt n log n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(log n)$ worst-case update time and $O(n^{2/3} log{frac{m}{n}})$ work.
The minimum-weight $2$-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of $1$ between each pair of vertices while the former strengthens this edge-connectivity requirement to $2$. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a $2$-approximation. In this paper, we give a deterministic distributed algorithm with round complexity of $widetilde{O}(D+sqrt{n})$ that computes a $(5+epsilon)$-approximation of 2-ECSS, for any constant $epsilon>0$. Up to logarithmic factors, this complexity matches the $widetilde{Omega}(D+sqrt{n})$ lower bound that can be derived from Das Sarma et al. [STOC11], as shown by Censor-Hillel and Dory [OPODIS17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC18], which achieved an $O(log n)$-approximation in $widetilde{O}(D+sqrt{n})$ rounds. We also present an alternative algorithm for $O(log n)$-approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network, following a framework introduced by Ghaffari and Haeupler [SODA16]. This algorithm has round complexity $widetilde{O}(D+sqrt{n})$ in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in $widetilde{O}(D)$ time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.
In the minimum $k$-edge-connected spanning subgraph ($k$-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to $k-1$ edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for $k geq 2$ less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for $k$-ECSS in the CONGEST model. Our first contribution is an $widetilde{O}(D + sqrt{n})$-round $O(log{n})$-approximation for 2-ECSS, for a graph with $n$ vertices and diameter $D$. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of $k$ we give an $widetilde{O}(n)$-round $O(log{n})$-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to $O(D log^3{n})$ rounds. All our results significantly improve the time complexity of previous algorithms.
Given an undirected, weighted graph, the minimum spanning tree (MST) is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication network, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes $O(m alpha(m, n))$ time, where $alpha(m, n)$ is the inverse Ackermanns function. Given the MST and sorted non-tree edges, our algorithm is the first that runs in $O(m+n)$ time and $O(m+n)$ space to find all replacement edges. Moreover, it is easy to implement and our experimental study demonstrates fast performance on several types of graphs. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
