English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The minimum-cost $k$-edge-connected spanning subgraph ($k$-ECSS) problem is ageneralization and strengthening of the well-studied minimum-cost spanning tree(MST) problem. While the round complexity of distributedly computing the latterhas been well-understood, the former remains mostly open, especially as soon as$k\geq 3$.  In this paper, we present the first distributed algorithm that computes anapproximation of $k$-ECSS in sublinear time for general $k$. Concretely, wedescribe a randomized distributed algorithm that, in$\tilde{O}(k(D+k\sqrt{n}))$ rounds, computes a $k$-edge-connected spanningsubgraph whose cost is within an $O(\log n\log k)$ factor of optimal. Here, $n$and $D$ denote the number of vertices and diameter of the graph, respectively.This time complexity is nearly optimal for any $k=poly(\log n)$, almostmatching an $\tilde{\Omega}(D+\sqrt{n/k})$ lower bound. Our algorithm is thefirst to achieve a sublinear round complexity for $k\geq 3$. We note that thiscase is considerably more challenging than the well-studied and well-understood$k=1$ case -- better known as MST -- and the closely related $k=2$ case.  Our algorithm is based on reducing the $k$-ECSS problem to $k$ set coverinstances, in which we gradually augment the connectivity of the spanningsubgraph. To solve each set cover instance, we combine new structuralobservations on minimum cuts with graph sketching ideas. One key ingredient inour algorithm is a novel structural lemma that allows us to compress theinformation about all minimum cuts in a graph into a succinct representation,which is computed in a decentralized fashion. We hope that this succinctrepresentation may find applications in other computational settings or forother problems.

A Nearly Time-Optimal Distributed Approximation of Minimum Cost $k$-Edge-Connected Spanning Subgraph