论文标题
几乎最佳的分布近似值的最低成本$ k $连接跨度子图
A Nearly Time-Optimal Distributed Approximation of Minimum Cost $k$-Edge-Connected Spanning Subgraph
论文作者
论文摘要
最低成本$ k $ - 连接子图（$ k $ -ecss）问题是对良好的最小成本生成树（MST）问题的概括和加强。虽然分布式计算后者的圆形复杂性已经得到了充分理解，但前者仍保持开放，尤其是$ k \ geq 3 $。 在本文中，我们介绍了第一个分布式算法，该算法计算$ k $ -ecss的近似于$ k $的$ k $ -ecss。具体而言，我们描述了一种随机分布式算法，该算法在$ \ tilde {o}（k（d+k \ sqrt {n} {n}））中$ rounds，计算一个$ k $ - 连接的跨度子段，其成本在$ o（\ log n \ log k）$ fimate oftim oftim oftim oftim oftim oftim oftim oftim oftim oftim oftim oftim oftim oftim optim oftim optim optim oftim oftim oftim。在这里，$ n $和$ d $分别表示图的顶点和直径。对于任何$ k = poly（\ log n）$，这个时间的复杂性几乎都是最佳的，几乎与$ \tildeΩ（d+\ sqrt {n/k}）$匹配。我们的算法是第一个以$ k \ geq 3 $实现透明圆的复杂性。我们注意到，这种情况比研究了良好且熟悉的$ k = 1 $案例（更名为MST）更具挑战性 - 以及密切相关的$ k = 2 $案例。 我们的算法基于将$ K $ -ECSS问题减少到$ K $ Set Cover Instances，在该实例中，我们逐渐增强了Spanning子图的连接性。为了解决每个设定的封面实例，我们将最小剪切的新结构观测与图形素描想法结合在一起。我们算法中的一种关键成分是一种新颖的结构引理，它使我们能够将图中所有最小切割的信息压缩为简洁的表示，该信息以分散的方式计算。我们希望这种简洁的表示可以在其他计算设置或其他问题中找到应用。
The minimum-cost $k$-edge-connected spanning subgraph ($k$-ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While the round complexity of distributedly computing the latter has 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 an approximation of $k$-ECSS in sublinear time for general $k$. Concretely, we describe a randomized distributed algorithm that, in $\tilde{O}(k(D+k\sqrt{n}))$ rounds, computes a $k$-edge-connected spanning subgraph 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)$, almost matching an $\tildeΩ(D+\sqrt{n/k})$ lower bound. Our algorithm is the first to achieve a sublinear round complexity for $k\geq 3$. We note that this case 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 cover instances, in which we gradually augment the connectivity of the spanning subgraph. To solve each set cover instance, we combine new structural observations on minimum cuts with graph sketching ideas. One key ingredient in our algorithm is a novel structural lemma that allows us to compress the information about all minimum cuts in a graph into a succinct representation, which is computed in a decentralized fashion. We hope that this succinct representation may find applications in other computational settings or for other problems.
