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

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第4期30卷 2217-2242页

作者： Rahman, Mustazee Univ Toronto Dept Math 40 St George St Toronto ON M5S 2E4 Canada

We study invariant percolation processes on the d-regular tree that are obtained as a factor of an iid process. We show that the density of any factor of iid site percolation process with finite clusters is asymptotically at most (log d)/d as d -> infinity. This bound is asymptotically optimal as it can be realized by independent sets. One implication of the result is a (1/2)-factor approximation gap, asymptotically in d, for estimating the density of maximal induced forests in locally tree-like d-regular graphs via factor of iid processes.

关键词： factor of iid induced forest percolation random regular graphs local algorithms

来源：评论

学校读者我要写书评

暂无评论

Ability to Count Messages Is Worth Θ (Δ) Rounds in Distributed Computing 16

Ability to Count Messages Is Worth Θ (Δ) Rounds in Distrib...

引用

31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS)

作者： Lempiainen, Tuomo Aalto Univ Dept Comp Sci Helsinki Inst Informat Technol Espoo Finland

ISBN: (纸本)9781450343916

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing one of which is the port-numbering model-and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2 Delta - 2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Delta lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.

关键词： distributed computing port-numbering model local algorithms lower bounds bisimulation

来源：评论

学校读者我要写书评

暂无评论

CARRE: Cellular Automaton based Redundant Readers Elimination in RFID Networks

CARRE: Cellular Automaton based Redundant Readers Eliminatio...

引用

IEEE International Conference on Communications (ICC)

作者： Rashid, Nafiul Choudhury, Salimur Salomaa, Kai Islamic Univ Technol Dept Comp Sci & Engn Dhaka Bangladesh Algoma Univ Dept Math & Comp Sci Sault Ste Marie ON Canada Queens Univ Sch Comp Kingston ON Canada

ISBN: (纸本)9781479966646

Redundant readers elimination is one of the fundamental optimization research problems in RFID networks. The problem is NP-hard and can be solved approximately using best known centralized set cover algorithms. However, either distributed or localized solutions for this problem are much more realistic and useful in practice. Different distributed and a few local algorithms are known in the literature. In this paper, we propose a cellular automaton based local algorithm for the redundant readers elimination optimization problem. To the best of our knowledge, this is the first cellular automaton based algorithm (that is, a strictly local algorithm) to solve this problem. We compare the performance of our algorithm with other local algorithms and establish that our algorithm gives much better results. We also compare our algorithm with the best known centralized approximation algorithm and find very competitive results even though our algorithm is a local one.

关键词： RFID Networks Readers Tags local algorithms Cellular Automata

来源：评论

学校读者我要写书评

暂无评论

Gathering a Closed Chain of Robots on a Grid 30

Gathering a Closed Chain of Robots on a Grid

引用

30th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Abshoff, Sebastian Cord-Landwehr, Andreas Fischer, Matthias Jung, Daniel Heide, Friedhelm Meyer auf der Univ Paderborn Heinz Nixdorf Inst Paderborn Germany Univ Paderborn Dept Comp Sci Paderborn Germany

ISBN: (纸本)9781509021406

We consider the following variant of the two-dimensional gathering problem for swarms of robots: Given a swarm of n indistinguishable, point-shaped robots on a two-dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a 2x2 subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision,...). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the viewing path length. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point, cannot be detected. Only based on the relative positions of its detectable chain neighbors, can a robot decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes the result from [1], where an open chain with specified distinguishable (and fixed) endpoints is considered.

关键词： gathering problem swarm formation problems autonomous robots distributed algorithms local algorithms mobile agents runtime bound

来源：评论

学校读者我要写书评

暂无评论

Lower bounds in distributed computing

Lower bounds in distributed computing

引用

作者： Juho Hirvonen Aalto University

学位级别：博士

In this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output. We study the local model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required? Many interesting problems, such as ﬁnding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the ﬁrst parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the ﬁrst lower bound for a natural graph problem that is linear in the maximum degree. In addition we study the power of unique in several contexts. We show that while usually unique identiﬁers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context oflocal decision, where the task

关键词： distributed computing local algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Foundation of Reactive local Topology Control

引用

IEEE COMMUNICATIONS LETTERS 2015年第7期19卷 1213-1216页

作者： Neumann, Florentin Frey, Hannes Univ Koblenz Landau Dept Comp Sci D-56070 Koblenz Germany

We formalize the concept reactive (aka contention-based or beaconless) topology control and its underlying problem statement. By means of message complexity, we define the classes of O(k)- and Omega(k)-reactive topology control algorithms which allow us to distinguish reactive from conventional local approaches and to classify the former. Moreover, based on our formalisms we prove two fundamental propositions regarding the reactive computability of standard topology control structures. Thus, our contribution not only establishes a taxonomy for identification of research gaps, but constitutes a theoretical foundation for profound investigation of this algorithm classes' principal power.

关键词： Ad hoc wireless networks reactive beaconless on-demand topology control local algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Heat Kernel Pagerank and a local Clustering Algorithm 1

引用

25th International Workshop on Combinatorial algorithms (IWOCA)

作者： Chung, Fan Simpson, Olivia Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (数字)9783319193151

ISBN: (纸本)9783319193151;9783319193144

Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time O(log(epsilon(-1)) log n/epsilon(3) log log(epsilon(-1))), assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio phi, many vertices in S may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance O(root phi).

关键词： Heat kernel pagerank Heat kernel local algorithms

来源：评论

学校读者我要写书评

暂无评论

Weak models of distributed computing, with connections to modal logic

引用

DISTRIBUTED COMPUTING 2015年第1期28卷 31-53页

作者： Hella, Lauri Jarvisalo, Matti Kuusisto, Antti Laurinharju, Juhana Lempiainen, Tuomo Luosto, Kerkko Suomela, Jukka Virtema, Jonni Univ Tampere Sch Informat Sci FIN-33101 Tampere Finland Univ Helsinki Dept Comp Sci HIIT SF-00510 Helsinki Finland Univ Wroclaw Inst Comp Sci PL-51151 Wroclaw Poland

This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering model, a node of degree d receives messages through d input ports and sends messages through d output ports, both numbered with 1, 2,..., d. In this work, VVc is the class of all graph problems that can be solved in the standard port-numbering model. We study the following subclasses of VVc: VV: Input port i and output port i are not necessarily connected to the same neighbour. MV: Input ports are not numbered;algorithms receive a multiset of messages. SV: Input ports are not numbered;algorithms receive a set of messages. VB: Output ports are not numbered;algorithms send the same message to all output ports. MB: Combination of MV and VB. SB: Combination of SV and VB. Now we have many trivial containment relations, such as SB subset of MB subset of VB subset of VV subset of VVc, but it is not obvious if, for example, either of VB subset of SV or SV subset of VB should hold. Nevertheless, it turns out that we can identify a linear order on these classes. We prove that SB (sic) MB = VB (sic) SV = MV = VV (sic) VVc. The same holds for the constant-time versions of these classes. We also show that the constant-time variants of these classes can be characterised by a corresponding modal logic. Hence the linear order identified in this work has direct implications in the study of the expressibility of modal logic. Conversely, one can use tools from modal logic to study these classes.

关键词： Distributed computing local algorithms Modal logic Models of computation

来源：评论

学校读者我要写书评

暂无评论

Oblivious algorithms for the Maximum Directed Cut Problem

引用

ALGORITHMICA 2015年第2期71卷 409-428页

作者： Feige, Uriel Jozeph, Shlomo Weizmann Inst Sci IL-76100 Rehovot Israel

This paper introduces a special family of randomized algorithms for Max DICUT that we call oblivious algorithms. Let the bias of a vertex be the ratio between the total weight of its outgoing edges and the total weight of all its edges. An oblivious algorithm selects at random in which side of the cut to place a vertex v, with probability that only depends on the bias of v, independently of other vertices. The reader may observe that the algorithm that ignores the bias and chooses each side with probability 1/2 has an approximation ratio of 1/4, whereas no oblivious algorithm can have an approximation ratio better than 1/2 (with an even directed cycle serving as a negative example). We attempt to characterize the best approximation ratio achievable by oblivious algorithms, and present results that are nearly tight. The paper also discusses natural extensions of the notion of oblivious algorithms, and extensions to the more general problem of Max 2-AND.

关键词： Linear programming local algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding Hidden Cliques of Size √N/e in Nearly Linear Time

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2015年第4期15卷 1069-1128页

作者： Deshpande, Yash Montanari, Andrea Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA

Consider an Erdos-Renyi random graph in which each edge is present independently with probability , except for a subset of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of Dekel et al. (ANALCO. SIAM, pp 67-75, 2011) provably identifies the clique in linear time, provided . Spectral methods can be shown to fail on cliques smaller than . In this paper we describe a nearly linear-time algorithm that succeeds with high probability for vertical bar C-N vertical bar (1 - epsilon) N/root e Delta for any epsilon > 0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on vertices). For large-girth regular graphs of degree (Delta + 1) we prove that so-called local algorithms succeed if vertical bar C-N vertical bar (1 - epsilon) N/root e Delta and fail if vertical bar C-N vertical bar (1 - epsilon) N/root e Delta.

关键词： Random graphs Average case complexity Approximate message passing Belief propagation local algorithms Sparse recovery

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：