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

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

来源：评论

学校读者我要写书评

暂无评论

A FAST SEGMENTATION-DRIVEN ALGORITHM FOR ACCURATE STEREO CORRESPONDENCE

A FAST SEGMENTATION-DRIVEN ALGORITHM FOR ACCURATE STEREO COR...

引用

International Conference on 3D Imaging (IC3D)

作者： Mattoccia, Stefano De-Maeztu, Leonardo Univ Bologna I-40126 Bologna Italy Univ Publ Navarra Pamplona Spain

ISBN: (纸本)9781479915781

Recent cost aggregation strategies that adapt their weights to image content enabled local algorithms to obtain results comparable to those of global algorithms based on more complex disparity optimization methods. Unfortunately, despite the potential advantages in terms of memory footprint and algorithmic simplicity compared to global algorithms, most of the state-of-the-art cost aggregation strategies deployed in local algorithms are extremely slow. In fact, their execution time is comparable and often worse than those of global approaches. In this paper we propose a framework for accurate and fast cost aggregation based on segmentation that allows us to obtain results comparable to state-of-the-art approaches much more efficiently (the execution time drops from minutes to seconds). A further speed-up is achieved taking advantage of multi-core capabilities available nowadays in almost any processor. The comparison with state-of-the-art cost aggregation strategies highlights the effectiveness of our proposal.

关键词： Stereo vision local algorithms cost aggregation segmentation adaptive weights

来源：评论

学校读者我要写书评

暂无评论

Distributed Convex Thresholding 15

Distributed Convex Thresholding

引用

34th Annual ACM Symposium on Principles of Distributed Computing (PODC)

作者： Wolff, Ran Yahoo Labs Haifa Israel

ISBN: (纸本)9781450336178

Over the last fifteen years, a large group of algorithms emerged which compute various predicates from distributed data with a focus on communication efficiency. These algorithms are often called "communication-efficient", "geometric-monitoring", or "local" algorithms. We jointly call them distributed convex thresholding algorithms, for reasons which will be explained in this work. Distributed convex thresholding algorithms have found their applications in domains in which bandwidth is a scarce resource, such as wireless sensor networks and peer-to-peer systems, or in scenarios in which data rapidly streams to the different processors but outcome of the predicate rarely changes. Common to all of these algorithms is the use of a data dependent criteria to determine when further messaging is required. This work presents two very simple yet exceedingly general theorems from which the correctness of all distributed convex thresholding algorithms can be elicited, and demonstrates that for key examples. Because the theorems are general, they extend the range of predicates which can be computed in a communication efficient manner beyond what is currently known. Unlike the previous correction proofs given to these algorithms, the proofs of the theorems presented here do not depend on the communication infrastructure. So the correctness of any distributed convex thresholding algorithm is immediately extended from broadcast enabled networks or from cycle free networks to general networks. Inspecting existing algorithms in light of the new theorems reveals that they contain redundant requirements, which cause them to send messages when indeed none are needed.

关键词： local algorithms Geometric monitoring Communication efficient algorithms Wireless sensor networks Peer-to-peer systems

来源：评论

学校读者我要写书评

暂无评论

What Can Be Approximated locally? Case Study: Dominating Sets in Planar Graphs 08

What Can Be Approximated Locally? Case Study: Dominating Set...

引用

20th ACM Symposium on Parallelism in algorithms and Architectures

作者： Lenzen, Christoph Oswald, Yvonne Anne Wattenhofer, Roger ETH Comp Engn & Networks Lab Zurich Switzerland

ISBN: (纸本)9781595939739

Whether local algorithms can compute constant approximations of NP-hard problems is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the approximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this paper, we present the first distributed algorithm approximating a minimum dominating set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information.

关键词： approximation distributed algorithms local algorithms dominating sets planar graphs

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds on localized Sensor Self-Deployment for Focused Coverage 24

Tight Bounds on Localized Sensor Self-Deployment for Focused...

引用

International Conference on Computer Communications and Networks ICCCN

作者： Sharma, Gokarna Krishnan, Hari Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA

ISBN: (纸本)9781479999644

We consider the self-deployment problem in mobile sensor networks with the objective of providing focused coverage for a point of interest (POI) such that the maximum area around it is covered by sensors without sensing holes. We present a local greedy algorithm, called TTGREEDY, that solves this problem in at most R + 2 . (n - 1) time steps, where R is the distance to the farthest initial sensor position from the POI and n is the number of sensors. This is a significant improvement over the best previously known O(D) time step algorithm of Blazovics and Lukovszki, where D is the sum of the initial distances to the sensors from the POI. The main idea is to synchronously drive mobile sensors along a locally-computed triangle tessellation avoiding collisions of sensors. We also show that there are initial configurations of n sensors in this problem where at least R+ (n-1)/2 time steps are needed by any greedy algorithm. These results provide the first tight runtime (within a small constant factor) solution to this problem.

关键词： Mobile sensor networks focused coverage self-deployment point of interest local algorithms runtime

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Anomaly Characterization in Large Scale Networks 44

Anomaly Characterization in Large Scale Networks

引用

44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Anceaume, Emmanuelle Busnel, Yann Le Merrer, Erwan Ludinard, Romaric Marchand, Jean-Louis Sericola, Bruno CNRS IRISA Paris France Univ Nantes LINA F-44035 Nantes France Technicolor Rennes Rennes France Inria Yvelines France Ecole Normale Super Rennes Rennes France

ISBN: (纸本)9781479922338

The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive errors from isolated ones, the former ones impacting a large number of nodes while the second ones affect solely a small number of them, or even a single one? The rationale of this question is twofold. First, from a theoretical point of view, we characterize errors with respect to their neighbourhood, and we show that there are error scenarios for which isolated and massive errors are indistinguishable from an omniscient observer point of view. We then relax the definition of this problem by introducing unresolved configurations, and exhibit necessary and sufficient conditions that allow any node to determine the type of errors it has been impacted by. These conditions only depend on the close neighbourhood of each node and thus are locally computable. We present algorithms that implement these conditions, and show through extensive simulations, thier performances. Now from a practical point of view, distinguishing isolated errors from massive ones is of utmost importance for networks providers. For instance, for Internet service providers that operate millions of home gateways, it would be very interesting to have procedures that allow gateways to self distinguish whether their dysfunction is caused by network-level errors or by their own hardware or software, and to notify the service provider only in the latter case.

关键词： Bismuth Measurement Monitoring Observers Peer-to-peer computing Quality of service Trajectory Error detection large scale systems local algorithms large-scale systems Peer to peer computing Error detection Quality of service bismuth trajectory Observers Gateways doorways internet service providers point of view

来源：评论

学校读者我要写书评

暂无评论

A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs

A Log-Star Distributed Maximal Independent Set Algorithm for...

引用

27th Annual ACM Symposium on Principles of Distributed Computing

作者： Schneider, Johannes Wattenhofer, Roger ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

ISBN: (纸本)9781595939890

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bonded graphs (GBG) our deterministic algorithm finishes in O(log*n) time, n being the, number of nodes. In light of Linial's Omega(log* n) lower bound our algorithm is asymptotically, v optimal. Our algorithm answers prominent open problems, in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit. disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta + 1 coloring in O(log'n) time, where delta is the maximum degree of the graph.

关键词： Ad Hoc Networks Sensor Networks Radio Networks Unit Disk Graphs Growth Bounded Graphs local algorithms Parallel algorithms Maximal Independent Sets Dominating Sets Connected Dominating Sets Coloring Symmetry Breaking

来源：评论

学校读者我要写书评

暂无评论

A local Algorithm for Finding Dense Subgraphs

引用

ACM TRANSACTIONS ON algorithms 2010年第4期6卷 1–12页

作者： Andersen, Reid Microsoft Corp 1 Microsoft Way Redmond WA 98052 USA

We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph G, a starting vertex v , and a parameter k, and outputs an induced subgraph of G. It is local in the sense that it does not examine the entire input graph;instead, it adaptively explores a region of the graph near the starting vertex. The running time of the algorithm is bounded by O(Delta k(2)), which depends on the maximum degree Delta, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph S with k' vertices and density theta, there exists a set S' subset of S for which the algorithm outputs a subgraph with density Omega(theta/log Delta) whenever v is an element of S' and k >= k'. We prove that S' contains at least half of the edges in S.

关键词： Dense subgraphs local algorithms spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

Study on the unweighted least-squares phase unwrapping algorithm

Study on the unweighted least-squares phase unwrapping algor...

引用

Conference on Holography, Diffractive Optics, and Applications IV

作者： Wang, Xuhui Zhang, Zhihui Guo, Zhongjia Wang, Huaying Handan Coll Sch Informat Engn Handan 056005 Hebei Peoples R China Hebei Univ Engn Sch Informat & Elect Engn Handan 056038 Peoples R China Hebei Univ Engn Coll Sci Handan 056038 Peoples R China

ISBN: (纸本)9780819483782

Two-dimensional phase unwrapping algorithm is the important step and key technology of three-dimensional shape measurement. In order to obtain the appearance characteristics of the object more accurately, a new phase unwrapping algorithm based on unweighted least-squares is presented in this paper, which is an improvement of discrete cosine transform (DCT) phase unwrapping algorithm. The advantage of this method is not only because of the global algorithms, processing the image as a whole, each pixel's value in the image is uniquely determined by solving the Discrete Poisson's equation with Newman boundary conditions which makes the least-squares solution of the wrapped and unwrapped phase difference minimum, but also can reduce the residues effectively. Through computer simulation, this new method and the original DCT algorithm were compared. Theoretical analysis and the results prove the validity of this method. The improved algorithm can eliminate the residues in the wrapped phase pictures more effectively. The phase information of the object can be reconstructed more accurately.

关键词： two-dimensional phase unwrapping algorithm three-dimensional shape measurement the least-squares phase unwrapping algorithm Discrete Poison equation Neumann boundary conditions discrete cosine transform global algorithms computer simulation local algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：