检索结果-内蒙古大学图书馆

Fast distributed approximation for TAP and 2-edge-connectivity

distributed COMPUTING 2020年第2期33卷 145-168页

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T boolean OR Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JaJa (SIAM J Comput 10(2):270-283, 1981). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (ACM Trans Algorithms 12(2):23, 2016). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC 2018), 2018), and approximations better than 2 for bounded weights (Adjiashvili in: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), 2017;Fiorini et al. in: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018. 10.1137/1.9781611975031.53). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T. When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D+root nlog*n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(h(MST)+root nlog*n)-round 3-approximation algorithm for the weighted case, where h(MST) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2.

关键词： distributed graph algorithms Approximation algorithms distributed network design Connectivity augmentation

来源：评论

学校读者我要写书评

暂无评论

distributed Spanner Approximation 18

Distributed Spanner Approximation

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450357951

We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result is that an a-approximation for the minimum directed k-spanner problem fork k >= 5 requires Omega(n/root alpha log n) rounds using deterministic algorithms or Omega(n/root alpha log n) rounds using randomized ones, in the CONGEST model of distributed computing. Combined with the constant-round O(n(epsilon))-approximation algorithm in the LOCAL model of [Barenboim, Elkin and Gavoille, 2016], as well as a polylog-round (1 + epsilon)-approximation algorithm in the LOCAL model that we show here, our lower bounds for the CONGEST model imply a strict separation between the LOCAL and CONGEST models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove a nearly-linear lower bound for the minimum weighted k-spanner problem for k >= 4, and we show lower bounds for the weighted 2-spanner problem. On the algorithmic side, apart from the aforementioned (1 + epsilon) approximation algorithm for minimum k-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of O (log(m/n)) for a graph with n vertices and m edges, which matches the best known ratio for polynomial time sequential algorithms [Kortsarz and Peleg, 1994], and is tight if we restrict ourselves to polynomial local computations. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem. It also provides a CONGEST algorithm for the minimum dominating set problem, with a guaranteed O (log Delta) approximation ratio.

关键词： approximation algorithms distributed network design spanners hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph 19

Improved Distributed Approximations for Minimum-Weight Two-E...

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Dory, Michal Ghaffari, Mohsen Technion Haifa Israel Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450362177

The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of thewell-studied minimumweight 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 (O) over tilde (D+root n) that computes a (9+epsilon)-approximation of 2-ECSS, for any constant epsilon > 0. Up to logarithmic factors, this complexity matches the (Omega) over tilde (D + root n) lower bound that can be derived from the technique of Das Sarma et al. [STOC'11], as shown by Censor-Hillel and Dory [OPODIS'17]. 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 [PODC'18], which achieved an O(log n)-approximation in (O) over tilde (D + root 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 [SODA'16]. This algorithm has round complexity (O) over tilde (D + root n) in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in (O) over tilde (D) time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.

关键词： distributed graph algorithms approximation algorithms distributed network design k-edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: distributed Approximation for Tree Augmentation 17

Brief Announcement: Distributed Approximation for Tree Augme...

引用

36th ACM Symposium on Principles of distributed Computing (PODC)

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450349925

A minimum spanning tree (MST) is an essential structure for distributed algorithms, since it is a low-cost connected subgraph which provides an efficient way to communicate in a network. However, trees cannot survive even one link failure. In this paper, we study the Tree Augmentation Problem (TAP), for which the input is a graph G and a spanning tree T of G and the goal is to augment T with a minimum (or minimum weight) set of edges Au. from G, such that T. Au. remains connected after a failure of any single link. Being central tasks for network design, TAP and additional connectivity augmentation problems have been well studied in the sequential setting. However, despite the distributed nature of these problems, they have not been studied in the distributed setting. We address this fundamental topic and provide a study of distributed TAP. In the full version of this paper, we present distributed 2-approximation algorithms for TAP, both for the un-weighted and weighted versions, which have a time complexity of O(h) rounds, where h is the height of T. We also present a distributed 4-approximation for unweighted TAP that has a time complexity ofO(root n log* n+D) rounds for a graphG with n vertices and diameter D, which is an improvement for large values of h. We complement our algorithms with lower bounds and some applications to related problems.

关键词： approximation algorithms distributed network design connectivity augmentation

来源：评论

学校读者我要写书评

暂无评论

distributed Approximation of Minimum k-edge-connected Spanning Subgraphs 18

Distributed Approximation of Minimum <i>k</i>-edge-connected...

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Dory, Michal Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450357951

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 > 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 (O) over tilde (D + root 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 (O) over tilde (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.

关键词： approximation algorithms distributed network design k-edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

The price of selfish behavior in bilateral network formation 05

The price of selfish behavior in bilateral network formation

引用

Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

作者： Jacomo Corbo David Parkes Harvard University

ISBN: (纸本)9781581139945

Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study the quality (price of anarchy) of equilibrium networks in a game where links require the consent of both participants and are negotiated bilaterally and compare these networks to those generated by an earlier model due to Fabrikant et al. [6] in which links are formed unilaterally. We provide a characterization of stable and efficient networks in the bilateral network formation game, show that the set of stable networks is richer than those in the unilateral game, and that all stable networks of the unilateral game are also stable in the bilateral game. We also provide an upper and lower bound on the price of anarchy (tight in the size of the network n but not the link cost α) of the bilateral game and show that the worst-case price of anarchy of the bilateral model is worse than for the unilateral model. A careful empirical analysis demonstrates that the average price of anarchy is better in the bilateral connection game than in the unilateral game for small link costs but worse as links become more expensive. In the process, a powerful equivalence between link-based graph stability and two game-theoretic equilibrium notions is also discussed. The equivalence establishes necessary and sufficient conditions for an equilibrium in the bilateral game that helps provide a partial geometric characterization of equilibrium graphs.

关键词： distributed network design game-theoretic models pairwise stability price of anarchy Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：