Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient and Simple Algorithms for Fault Tolerant Spanners
420
0
0.0
(
0
)
Added by
Michael Dinitz
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known polynomial time algorithm is significantly suboptimal. Designing a polynomial-time algorithm to construct (near-)optimal fault-tolerant spanners was given as an explicit open problem in the two most recent papers on fault-tolerant spanners ([Bodwin, Dinitz, Parter, Vassilevka Williams SODA 18] and [Bodwin, Patel PODC 19]). We give a surprisingly simple algorithm which runs in polynomial time and constructs fault-tolerant spanners that are extremely close to optimal (off by only a linear factor in the stretch) by modifying the greedy algorithm to run in polynomial time. To complement this result, we also give simple distributed constructions in both the LOCAL and CONGEST models.
rate research
Read More
Recent work has established that, for every positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges that is resilient to $f$ edge or vertex faults. For vertex faults, this bound is tight. However, the case of edge faults is not as well understood: the best known lower bound for general $k$ is $Omega(f^{frac12 - frac{1}{2k}} n^{1+1/k} +fn)$. Our main result is to nearly close this gap with an improved upper bound, thus separating the cases of edge and vertex faults. For odd $k$, our new upper bound is $O_k(f^{frac12 - frac{1}{2k}} n^{1+1/k} + fn)$, which is tight up to hidden $poly(k)$ factors. For even $k$, our new upper bound is $O_k(f^{1/2} n^{1+1/k} +fn)$, which leaves a gap of $poly(k) f^{1/(2k)}$. Our proof is an analysis of the fault-tolerant greedy algorithm, which requires exponential time, but we also show that there is a polynomial-time algorithm which creates edge fault tolerant spanners that are larger only by factors of $k$.
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes $widetilde{O}left( f^{1-1/k} n^{2+1/k} + mf^2right)$ time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC 19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms -- usually sublogarithmic-time and often $poly(loglog n)$-time, or even faster -- for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present $poly(log k) in poly(loglog n)$ round MPC algorithms for computing $O(k^{1+{o(1)}})$-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an $O(log^2log n)$-round algorithm for $O(log^{1+o(1)} n)$ approximation of all pairs shortest paths (APSP) in the near-linear regime of local memory. To the best of our knowledge, this is the first sublogarithmic-time MPC algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model.
The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as, improved FT routing schemes. For a given $n$-vertex graph $G$ and a bound $f$ on the number of faults, an $f$-FT connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of the vertices $s$ and $t$, and at most $f$ failing edges $F$, one can determine if $s$ and $t$ are connected in $G setminus F$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS 07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an $n$-vertex graph and a fault bound $f$ are: -- There is a randomized FT connectivity labeling scheme with a label length of $O(f+log n)$ bits, hence optimal for $f=O(log n)$. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG 11]. -- There is a randomized FT connectivity labeling scheme with a label length of $O(log^3 n)$ bits (independent of the number of faults $f$). This scheme is based on the notion of linear sketches of [Ahn et al., SODA 12]. -- For $kgeq 1$, there is a randomized routing scheme that routes a message from $s$ to $t$ in the presence of a set $F$ of faulty edges, with stretch $O(|F|^2 k)$ and routing tables of size $tilde{O}(f^3 n^{1/k})$. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP 11], providing the first scheme with sub-linear FT labeling and routing schemes for general graphs.
We consider the distributed version of the Multiple Knapsack Problem (MKP), where $m$ items are to be distributed amongst $n$ processors, each with a knapsack. We propose different distributed approximation algorithms with a tradeoff between time and message complexities. The algorithms are based on the greedy approach of assigning the best item to the knapsack with the largest capacity. These algorithms obtain a solution with a bound of $frac{1}{n+1}$ times the optimum solution, with either $mathcal{O}left(mlog nright)$ time and $mathcal{O}left(m nright)$ messages, or $mathcal{O}left(mright)$ time and $mathcal{O}left(mn^{2}right)$ messages.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
