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

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

来源：评论

学校读者我要写书评

暂无评论

k-Center Clustering in distributed Models 31st

k-Center Clustering in Distributed Models

引用

31st International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Biabani, Leyla Paz, Ami Eindhoven Univ Technol Eindhoven Netherlands LISN CNRS Paris France Paris Saclay Univ Paris France

ISBN: (纸本)9783031606021;9783031606038

The k-center problem is a central optimization problem with numerous applications for machine learning, data mining, and communication networks. Despite extensive study in various scenarios, it surprisingly has not been thoroughly explored in the traditional distributed setting, where the communication graph of a network also defines the distance metric. We initiate the study of the k-center problem in a setting where the underlying metric is the graph's shortest path metric in three canonical distributed settings: the local, congest, and clique models. Our results encompass constant-factor approximation algorithms and lower bounds in these models, as well as hardness results for the bi-criteria approximation setting.

关键词： k-Center clustering distributed graph algorithms Shortest path metric

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of distributed Splitting Problems 19

On the Complexity of Distributed Splitting Problems

引用

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

作者： Bamberger, Philipp Ghaffari, Mohsen Kuhn, Fabian Maus, Yannic Uitto, Jara Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland Technion Haifa Israel

ISBN: (纸本)9781450362177

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly logn-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G = (V, E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly logn-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results: center dot We obtain efficient algorithms for special cases of weak splitting in nearly regular graphs. We show that if delta = Omega(log n) and Delta are the minimum and maximum degrees of G, weak splitting can be solved deterministically in time O(Delta/delta center dot poly(log n)). Further, if delta = Omega(log log n) and Delta <= 2(epsilon delta), the time complexity is O(Delta/delta center dot poly(log log n)). center dot We prove that the following two related problems are also complete in the same sense: (I) Color the nodes of a graph with C <= poly log n colors such that each node with a sufficiently large polylogarithmic degree has at least 2 log n different colors among its neighbors, and (II) Color the nodes with a large constant number of colors so that for each node of a sufficiently large at least logarithmic degree d(v), the number of neighbors o

关键词： distributed graph algorithms weak splitting LOCAL Model distributed symmetry breaking randomness

来源：评论

学校读者我要写书评

暂无评论

The topology of local computing in networks

引用

Journal of Applied and Computational Topology 2024年第4期8卷 1069-1098页

作者： Fraigniaud, Pierre Paz, Ami Institut de Recherche en Informatique Fondamentale CNRS Université Paris Cité Laboratoire Interdisciplinaire des Sciences du Numérique CNRS Université Paris-Saclay

For more than three decades, distributed systems have been described and analyzed using topological tools, primarily using two techniques: protocol complexes and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects (typically a shared memory consisting of a collection of read-write registers) or message-passing enabling direct communication between any pair of processes. This paper aims to examine the use of protocol complexes in the study of network computing. In this case, processes are located at the network nodes and communicate by exchanging messages only along the network’s edges (i.e., not every pair of processes can directly communicate). There are several reasons why applying the topological approach to network computing can be challenging, and a prominent one is that node identifiers yield protocol complexes whose sizes grow exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or the network size. We leverage this independence to meet the above challenge and present local protocol complexes, whose sizes do not depend on the network size. As an application of the “compacted” protocol complexes, we reformulate the celebrated lower bound of Ω(log^∗n) rounds for 3-coloring the n-node ring in the topological framework. © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.

关键词： Combinatorial topology distributed algorithms distributed computing distributed graph algorithms Theory of computation

来源：评论

学校读者我要写书评

暂无评论

Distance Computations in the Hybrid Network Model via Oracle Simulations 38

Distance Computations in the Hybrid Network Model via Oracle...

引用

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Censor-Hillel, Keren Leitersdorf, Dean Polosukhin, Volodymyr Technion Israel Inst Technol Haifa Israel

ISBN: (纸本)9783959771801

The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from (O) over tilde (n(1/3)) sources which completes in (O) over tilde (n(1/3)) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC '20], which computes shortest paths from a single source in (O) over tilde (n(2/5)) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1 + epsilon)-approximation for unweighted diameter, both in (O) over tilde (n(1/3)) rounds w.h.p., which is comparable to the (Omega) over tilde (n(1/3)) lower bound of [Kuhn and Schneider, PODC '20] for a (2 - epsilon)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities.

关键词： distributed graph algorithms Hybrid network model Distance computations

来源：评论

学校读者我要写书评

暂无评论

Can We Break Symmetry with o(m) Communication? 21

Can We Break Symmetry with <i>o</i>(<i>m</i>) Communication?

引用

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

作者： Pai, Shreyas Pandurangan, Gopal Pemmaraju, Sriram, V Robinson, Peter Univ Iowa Iowa City IA 52242 USA Univ Houston Houston TX USA City Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450385480

We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less is known about the message complexity of these problems. In fact, all known algorithms need at least Omega(m) communication for these problems, where m is the number of edges in the graph. We address the following question in this paper: can we solve problems such as coloring and MIS using sublinear, i.e., o(m) communication, and if so under what conditions? In a classical result, Awerbuch, Goldreich, Peleg, and Vainish [JACM 1990] showed that fundamental global problems such as broadcast and spanning tree construction require at least Omega(m) messages in the KT-1 CONGEST model (i.e., CONGEST model in which nodes have initial knowledge of the neighbors' ID's) when algorithms are restricted to be comparison-based (i.e., algorithms in which node ID's can only be compared). Thirty five years after this result, King, Kutten, and Thorup [PODC 2015] showed that one can solve the above problems using (O) over tilde (n) messages (n is the number of nodes in the graph) in (O) over tilde (n) rounds in the KT-1 CONGEST model if non-comparison-based algorithms are permitted. An important implication of this result is that one can use the synchronous nature of the KT-1 CONGEST model, using silence to convey information, and solve any graph problem using non-comparison-based algorithms with (O) over tilde (n) messages, but this takes an exponential number of rounds. In the asynchronous model, even this is not possible. In contrast, much less is known about the message complexity of local symmetry breaking problems such as coloring and MIS. Our paper fills this gap by presenting the following results. Lower bounds: In the KT-1 CONGEST model, we show that any comparison-based algorithm, even a randomized Monte-Carlo algorithm with

关键词： distributed graph algorithms Congest Model Message Complexity Symmetry Breaking MIS Coloring

来源：评论

学校读者我要写书评

暂无评论

Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions 22

Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expa...

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Chang, Yi-Jun Su, Hsin-Hao Natl Univ Singapore Singapore Singapore Boston Coll Boston MA 02467 USA

ISBN: (纸本)9781450392624

Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 +/-epsilon) factors in poly(log n, 1/epsilon) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1 - epsilon)-approximate maximum weighted matching can be computed in poly(log n, 1/epsilon) rounds in the CONGEST model. In this paper, we develop a generic framework for obtaining poly(log n, 1/epsilon)-round (1 +/- epsilon)-approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the CONGEST model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs. Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & distributed Computing 2021]. Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a

关键词： distributed graph algorithms expander decompositions matching

来源：评论

学校读者我要写书评

暂无评论

On distributed Computation of the Minimum Triangle Edge Transversal 31st

On Distributed Computation of the Minimum Triangle Edge Tran...

引用

31st International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Censor-Hillel, Keren Khoury, Majd Technion Haifa Israel

ISBN: (纸本)9783031606021;9783031606038

The distance of a graph from being triangle-free is a fundamental graph parameter, counting the number of edges that need to be removed from a graph in order for it to become triangle-free. Its corresponding computational problem is the classic minimum triangle edge transversal problem, and its normalized value is the baseline for triangle-freeness testing algorithms. While triangle-freeness testing has been successfully studied in the distributed setting, computing the distance itself in a distributed setting is unknown, to the best of our knowledge, despite being well-studied in the centralized setting. This work addresses the computation of the minimum triangle edge transversal in distributed networks. We show with a simple warm-up construction that this is a global task, requiring Omega(D) rounds even in the LOCAL model with unbounded messages, where D is the diameter of the network. However, we show that approximating this value can be done much faster. A (1+epsilon)-approximation can be obtained in poly log n rounds, where n is the size of the network graph. Moreover, faster approximations can be obtained, at the cost of increasing the approximation factor to roughly 3, by a reduction to the minimum hypergraph vertex cover problem. With a time overhead of the maximum degree Delta, this can also be applied to the CONGEST model, in which messages are bounded. Our key technical contribution is proving that computing an exact solution is "as hard as it gets" in CONGEST, requiring a near-quadratic number of rounds. Because this problem is an edge selection problem, as opposed to previous lower bounds that were for node selection problems, major challenges arise in constructing the lower bound, requiring us to develop novel ingredients.

关键词： distributed graph algorithms Distance from triangle-freeness Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Deterministic distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition 62

Deterministic Distributed Vertex Coloring: Simpler, Faster, ...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Ghaffari, Mohsen Kuhn, Fabian Swiss Fed Inst Technol Dept Comp Sci CH-8092 Zurich Switzerland Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

ISBN: (纸本)9781665420556

We present a simple deterministic distributed algorithm that computes a (Delta+1)-vertex coloring in O(log(2) Delta center dot log n) rounds. The algorithm can be implemented with O(log n)-bit messages. The algorithm can also be extended to the more general (degree + 1)-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for (Delta + 1)-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozho.n and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an O(log(5) n)-round algorithm for (Delta + 1)-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for (Delta + 1)-coloring, now reaching the bound of O(log(3) log n) rounds. As a further application, we provide faster deterministic distributed algorithms for the following vertex coloring variants. In graphs of arboricity a, we show that a (2 + epsilon)a-vertex coloring can be computed in O(log(3) a center dot log n) rounds. We also show that for Delta >= 3, a Delta-coloring of a Delta-colorable graph G can be computed in O(log(2) Delta center dot log(2) n) rounds.

关键词： distributed graph algorithms distributed coloring deterministic rounding list coloring

来源：评论

学校读者我要写书评

暂无评论

The distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees 15

The Distributed Complexity of Locally Checkable Labeling Pro...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Chang, Yi-Jun Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9783959773096

We consider locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible complexities of LCL problems. For example, it has been established that there are no LCL problems exhibiting deterministic complexities falling between omega(log* n) and o(log n). This line of inquiry has yielded a wealth of algorithmic techniques and insights that are useful for algorithm designers. While the complexity landscape of LCL problems on general graphs, trees, and paths is now well understood, graph classes beyond these three cases remain largely unexplored. Indeed, recent research trends have shifted towards a fine-grained study of special instances within the domains of paths and trees. In this paper, we generalize the line of research on characterizing the complexity landscape of LCL problems to a much broader range of graph classes. We propose a conjecture that characterizes the complexity landscape of LCL problems for an arbitrary class of graphs that is closed under minors, and we prove a part of the conjecture. Some highlights of our findings are as follows. We establish a simple characterization of the minor-closed graph classes sharing the same deterministic complexity landscape as paths, where O(1), Theta(log* n), and Theta(n) are the only possible complexity classes. It is natural to conjecture that any minor-closed graph class shares the same complexity landscape as trees if and only if the graph class has bounded treewidth and unbounded pathwidth. We prove the "only if" part of the conjecture. For the class of graphs with pathwidth at most k, we show the existence of LCL problems with randomized and deterministic complexities Theta(n), Theta(n(1/2)), Theta(n(1/3)),..., Theta(n(1/k)) and the non-existence of LCL problems whose deterministic complexity is between omega(log* n) and o(n(1/k)). Consequently, in addition to the well-known complexity landscapes for paths, tre

关键词： distributed graph algorithms locality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：