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

Estimation of Intrinsic Volumes from Digital Grey-Scale Images

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2014年第2期49卷 352-376页

作者： Svane, Anne Marie Aarhus Univ Dept Math DK-8000 Aarhus C Denmark

local algorithms are common tools for estimating intrinsic volumes from black-and-white digital images. However, these algorithms are typically biased in the design based setting, even when the resolution tends to infinity. Moreover, images recorded in practice are most often blurred grey-scale images rather than black-and-white. In this paper, an extended definition of local algorithms, applying directly to grey-scale images without thresholding, is suggested. We investigate the asymptotics of these new algorithms when the resolution tends to infinity and apply this to construct estimators for surface area and integrated mean curvature that are asymptotically unbiased in certain natural settings.

关键词： Digital grey-scale images local algorithms Design based set-up Surface area Integrated mean curvature

来源：评论

学校读者我要写书评

暂无评论

Connectivity preserving obstacle avoidance localized motion planning algorithms for mobile wireless sensor networks

引用

PEER-TO-PEER NETWORKING AND APPLICATIONS 2019年第3期12卷 647-659页

作者： Hassan, Md. Yeakub Hussain, Faisal Choudhury, Salimur Green Univ Bangladesh Dept Comp Sci & Engn Dhaka Bangladesh Islamic Univ Technol Dept Comp Sci & Engn Gazipur Bangladesh Lakehead Univ Dept Comp Sci Thunder Bay ON Canada

Mobile wireless sensor networks (MWSN) are better in terms of coverage and it plays an important role in ubiquitous wireless networks. We design Cellular Automaton (CA) based localized motion planning algorithms for mobile wireless sensors. We propose cellular automaton based algorithms for both dispersion and gathering problems. The dispersion algorithm is intended for self-deployment purpose with the goal of increasing the sensing coverage of the network. We apply a probabilistic approach that maximizes the network coverage as well as maintains the connectivity of the network. In addition, after finishing the dispersion, a gathering algorithm guides the sensors to round up to a single place for collection. It is noteworthy that both algorithms are synchronous which means that all sensors run algorithms in parallel at the same time. Moreover, our algorithms allow the sensors to avert obstacles in their path of movement. As cellular automaton functions depend on the local information about the network strictly, they are suitable for MWSN in practice. We evaluate the performance of our algorithm based on some defined metrics i.e., coverage, strongly connected coverage. We find that our dispersion algorithm maintains better coverage than state-of-the-art algorithm. Furthermore, in case of synchronous gathering, sensors get disconnected for some cases to form multiple clusters while using state-of-the-art algorithm, but our proposed gathering algorithm is always able to provide the connectivity.

关键词： Self-deployment Synchronous gathering Mobile wireless sensor network (MWSN) local algorithms Cellular automaton IoT Obstacles

来源：评论

学校读者我要写书评

暂无评论

Almost Stable Matchings by Truncating the Gale-Shapley Algorithm

引用

ALGORITHMICA 2010年第1期58卷 102-118页

作者： Floreen, Patrik Kaski, Petteri Polishchuk, Valentin Suomela, Jukka Univ Helsinki HIIT FIN-00014 Helsinki Finland

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose-accept rounds executed by the Gale-Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance;for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+epsilon)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

关键词： Distributed stable matching Almost stable matching local algorithms Constant-time randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 29-40页

作者： Li, Shouwei Heide, Friedhelm Meyer auf der Podlipyan, Pavel Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Dept Comp Sci Furstenallee 11 D-33102 Paderborn Germany

In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n(2)) for gathering in two dimensions Euclidean space, and O(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this "collisionless property" of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the "collisionless property" holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center alg

关键词： local algorithms Distributed algorithms Collisionless gathering Mobile robots Multiagent system

来源：评论

学校读者我要写书评

暂无评论

A continuous strategy for collisionless gathering

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 41-60页

作者： Li, Shouwei Markarian, Christine Heide, Friedhelm Meyer Auf Der Podlipyan, Pavel Paderborn Univ Heinz Nixdorf Inst Paderborn Germany Paderborn Univ Dept Comp Sci Paderborn Germany Univ Dubai Dept Engn & Informat Technol Dubai U Arab Emirates

Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O (nd) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art. (C) 2020 Elsevier B.V. All rights reserved.

关键词： local algorithms Distributed algorithms Collisionless gathering Mobile robots Multiagent system

来源：评论

学校读者我要写书评

暂无评论

Association rule mining in peer-to-peer systems

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS 2004年第6期34卷 2426-2438页

作者： Wolff, R Schuster, A Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We extend the problem of association rule mining-a key data mining problem-to systems in which the database is partitioned among a very large number of computers that are dispersed over a wide area. Such computing systems include grid computing platforms, federated database systems, and peer-to-peer computing environments. The scale of these systems poses several difficulties, such as the impracticality of global communications and global synchronization, dynamic topology changes of the network, on-the-fly data updates, the need to share resources with other applications, and the frequent failure and recovery of resources. We present an algorithm by which every node in the system can reach the exact solution, as if it were given the combined database. The algorithm is entirely asynchronous, imposes very little communication overhead, transparently tolerates network topology changes and node failures, and quickly, adjusts to changes in the data as they occur. Simulation of up to 10000 nodes show that the algorithm is local: all rules, except for those whose confidence is about equal to the confidence threshold, are discovered using information gathered from a very small vicinity, whose size is independent of the size of the system.

关键词： anytime algorithms association rule-mining data mining local algorithms peer-to-peer

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

FACTOR OF IID PERCOLATION ON TREES

引用

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

来源：评论

学校读者我要写书评

暂无评论

Community detection using preference networks

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2018年 495卷 126-136页

作者： Tasgin, Mursel Bingol, Haluk O. Bogazici Univ Dept Comp Engn Istanbul Turkey

Community detection is the task of identifying clusters or groups of nodes in a network where nodes within the same group are more connected with each other than with nodes in different groups. It has practical uses in identifying similar functions or roles of nodes in many biological, social and computer networks. With the availability of very large networks in recent years, performance and scalability of community detection algorithms become crucial, i.e. if time complexity of an algorithm is high, it cannot run on large networks. In this paper, we propose a new community detection algorithm, which has a local approach and is able to run on large networks. It has a simple and effective method;given a network, algorithm constructs a preference network of nodes where each node has a single outgoing edge showing its preferred node to be in the same community with. In such a preference network, each connected component is a community. Selection of the preferred node is performed using similarity based metrics of nodes. We use two alternatives for this purpose which can be calculated in 1-neighborhood of nodes, i.e. number of common neighbors of selector node and its neighbors and, the spread capability of neighbors around the selector node which is calculated by the gossip algorithm of Lind ***. Our algorithm is tested on both computer generated LFR networks and real-life networks with ground truth community structure. It can identify communities accurately in a fast way. It is local, scalable and suitable for distributed execution on large networks. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Complex networks Community detection local algorithms Gossip spreading

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for sensor networks

引用

PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES 2012年第1958期370卷 11-26页

作者： Lenzen, Christoph Wattenhofer, Roger Hebrew Univ Jerusalem Sch Engn & Comp Sci IL-91904 Jerusalem Israel ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

Distributed algorithms are an established tool for designing protocols for sensor networks. In this paper, we discuss the relation between distributed computing theory and sensor network applications. We also present ... 详细信息

关键词： local algorithms topology of sensor networks interference models maximal independent set vertex colouring clock synchronization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：