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

The complexity of leader election in diameter-two networks

DISTRIBUTED COMPUTING 2020年第2期33卷 189-205页

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Houston TX 77204 USA McMaster Univ Hamilton ON Canada

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1-7:27, 2015) showed a fundamental lower bound of Omega(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability;this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134-143, 2015) established a tight bound of (Theta) over tilde(root n) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of (Theta) over tilde (n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n(-c), for some fixed positive constant c) succeeds and uses O(n log(3) n) messages and runs in O(1) rounds;this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs O(n) messages (even when n is known), regardless of the number of rounds. We also present an O(n log n) message deterministic algorithm that takes O(log n) rounds (but needs knowledge of n);we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-a-vis the graph diameter.

关键词： Distributed algorithm Leader election randomized algorithm Message complexity Time complexity Lower bound

来源：评论

学校读者我要写书评

暂无评论

An Improved randomized Circle Detection algorithm Using in Printed Circuit Board Locating Mark

引用

Applied Mathematics 2019年第10期10卷 848-861页

作者： Jingkun Liu Qi Fan Chengyi University College Jimei UniversityXiamenChina Xiamen Sinic-Tek Intelligent Technology Co. Ltd.XiamenChina

This paper presents an improved randomized Circle Detection (RCD) algorithm with the characteristic of circularity to detect randomized circle in images with complex background, which is not based on the Hough Transform. The experimental results denote that this algorithm can locate the circular mark of Printed Circuit Board (PCB).

关键词： Circle Detection randomized algorithm Characteristic of Circularity Printed Circuit Board

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

引用

JOURNAL OF THE ACM 2020年第6期67卷 1–22页

作者： Chakraborty, Diptarka Das, Debarati Goldenberg, Elazar Koucky, Michal Saks, Michael Natl Univ Singapore Sch Comp 13 Comp Dr Singapore 117417 Singapore Univ Copenhagen Univ Pk 1 DK-2100 Copenhagen Denmark Acad Coll Tel Aviv Yaffo Rabenu Yeruham St IL-61083 Yaffo Israel Charles Univ Prague Malostranske Nam 25 Prague 11800 Czech Republic Rutgers State Univ Dept Math 110 Frelinghuysen Rd Piscataway NJ USA

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time (O) over tildeO(n(2-2/7)) that approximates the edit distance within a constant factor.

关键词： Edit distance approximation algorithm sub-quadratic time algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A MAPREDUCE algorithm FOR MINIMUM VERTEX COVER PROBLEMS AND ITS RANDOMIZATION

引用

COMPUTING AND INFORMATICS 2020年第5期39卷 952-972页

作者： Nakamura, Morikazu Kinjo, Daiki Yoshida, Takeo Univ Ryukyus Fac Engn Nishihara Okinawa 9030213 Japan

MapReduce is a programming paradigm for large-scale distributed information processing. This paper proposes a MapReduce algorithm for the minimum vertex cover problem, which is known to be NP-hard. The MapReduce algorithm can efficiently obtain a minimal vertex cover in a small number of rounds. We show the effectiveness of the algorithm through experimental evaluation and comparison with exact and approximate algorithms which demonstrates a high quality in a small number of MapReduce rounds. We also confirm from experimentation that the algorithm has good scalability allowing high-quality solutions under restricted computation times due to increased graph size. Moreover, we extend our algorithm to randomized one to obtain a good expected approximate ratio.

关键词： MapReduce minimum vertex cover Hadoop optimization algorithm design randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Voltage Control for Distribution Networks via Coordinated Regulation of Active and Reactive Power of DGs

引用

IEEE TRANSACTIONS ON SMART GRID 2020年第5期11卷 4017-4031页

作者： Hu, Xiong Liu, Zhi-Wei Wen, Guanghui Yu, Xinghuo Liu, Chen Huazhong Univ Sci & Technol Sch Artificial Intelligence & Automat Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Key Lab Image Proc & Intelligent Control Minist Educ Wuhan 430074 Peoples R China Southeast Univ Sch Math Dept Syst Sci Nanjing 210096 Peoples R China RMIT Univ Sch Engn Melbourne Vic 3001 Australia

Fast-acting reactive power support from distributed generations (DGs) is a promising approach for tackling rapid voltage fluctuations in distribution networks. However, the voltage regulation range via reactive power of DGs alone is narrow especially in distribution networks with high resistance-reactance ratio. In this paper, a randomized algorithm is proposed to improve the voltage profile in distribution networks via coordinated regulation of the active and reactive power of DGs. To this end, first the variables of the proposed quadratically constrained quadratic programming problem on voltage control are partitioned into disjoint subsets, each of which corresponds to a unique low-dimensional subproblem. Second, these subsets are updated serially in a randomized manner via solving their corresponding subproblems, which overcomes the requirement for system-wide coordination among participating agents and guarantees an optimal solution. Compared with the existing algorithms, the proposed algorithm is resilient to network reconfigurations and achieves a wider voltage regulation range. The effectiveness and convergence performance of the proposed algorithm is validated by the case studies.

关键词： Reactive power Voltage control Distribution networks Regulation Partitioning algorithms Quadratic programming Convergence Voltage control distribution network coordinated regulation quadratically constrained quadratic programming randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Targeted Protection Maximization in Social Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第3期7卷 1645-1655页

作者： Guo, Jianxiong Li, Yi Wu, Weili Univ Texas Dallas Dept Comp Sci Erik Jonsson Sch Engn & Comp Sci Richardson TX 75080 USA Univ Texas Tyler Dept Comp Sci Soules Coll Business Tyler TX 75799 USA

Even though the widespread use of social platforms provides convenience to our daily life, it causes some bad results at the same time. For example, misinformation and personal attack can be spread easily on social networks, which drives us to study how to block the spread of misinformation effectively. Unlike the classical rumor blocking problem, we study how to protect the targeted users from being influenced by rumor, called targeted protection maximization (TPM). It aims to block the least edges such that the expected ratio of nodes in targeted set influenced by rumor is at most beta. Under the IC-model, the objective function of TPM is monotone non-decreasing, but not submodular and not supermodular, which makes it difficult for us to solve it by existing algorithms. In this paper, we propose two efficient techniques to solve TPM problem, called Greedy and General-TIM. The Greedy uses simple Hill-Climbing strategy, and get a theoretical bound, but the time complexity is hard to accept. The second algorithm, General-TIM, is formed by means of randomized sampling by Reverse Shortest Path (Random-RS-Path), which reduces the time consuming significantly. A precise approximation ratio cannot be promised in General-TIM, but in fact, it can get good results in reality. Considering the community structure in networks, both Greedy and General-TIM can be improved after removing unrelated communities. Finally, the effectiveness and efficiency of our algorithms is evaluated on several real datasets.

关键词： Targeted Protection Maximization rumor blocking social network randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact simulation of first exit times for one-dimensional diffusion processes

引用

ESAIM-MATHEMATICAL MODELLING AND NUMERICAL ANALYSIS-MODELISATION MATHEMATIQUE ET ANALYSE NUMERIQUE 2020年第3期54卷 811-844页

作者： Herrmann, Samuel Zucca, Cristina Univ Bourgogne Franche Comte CNRS UMR 5584 Inst Math Bourgogne F-21000 Dijon France Univ Turin Dept Math G Peano Via Carlo Alberto 10 I-10123 Turin Italy

The simulation of exit times for diffusion processes is a challenging task since it concerns many applications in different fields like mathematical finance, neuroscience, reliability horizontal ellipsis The usual procedure is to use discretization schemes which unfortunately introduce some error in the target distribution. Our aim is to present a new algorithm which simulates exactly the exit time for one-dimensional diffusions. This acceptance-rejection algorithm requires to simulate exactly the exit time of the Brownian motion on one side and the Brownian position at a given time, constrained not to have exit before, on the other side. Crucial tools in this study are the Girsanov transformation, the convergent series method for the simulation of random variables and the classical rejection sampling. The efficiency of the method is described through theoretical results and numerical examples.

关键词： Exit time Brownian motion diffusion processes Girsanov's transformation rejection sampling exact simulation randomized algorithm conditioned Brownian motion

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for UAVs Group Flight Optimization

引用

IFAC Proceedings Volumes 2013年第11期46卷 205-208页

作者： Konstantin Amelin Natalia Amelina Oleg Granichin Olga Granichina Boris Andrievsky St. Petersburg State University St. Petersburg Russia Norwegian University of Science and Technology Department of Telematics Trondheim Norway Institute for Problems of Mechanical Engineering of RAS Russia Saint Petersburg National Research University of Information Technologies Mechanics and Optics St. Petersburg Russia

The problem of small UAVs flight optimization is considered. To solve this problem thermal updrafts are used. For the precise detection of the thermal updrafts center the simultaneous perturbation stochastic approximation (SPSA) type algorithm is proposed. If UAVs use thermal updrafts so they can save the energy during the flight. Therefore the flight time will be vary for different UAVs. In order to optimize the area monitoring, the consensus approach has been proposed.

关键词： Unmanned aerial vehicle (UAV) UAVs network UAVs group simultaneous perturbation stochastic approximation randomized algorithm consensus

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for Roadside Units Placement in Vehicular Ad Hoc Network

A Randomized Algorithm for Roadside Units Placement in Vehic...

引用

IEEE 9th International Conference on Mobile Ad-hoc and Sensor Networks (MSN)

作者： Xu Liya Huang Chuanhe Li Peng Zhu Junyu Wuhan Univ Sch Comp Wuhan 430072 Peoples R China

ISBN: (纸本)9780769551593

In this paper, we investigate the problem of optimal road side units (RSUs) placement in Vehicular Ad Hoc Network (VANET) on a highway, which enables the VANET maintain a good connectivity. Our goal is to find out minimal number of road side units, such that the vehicles could communicate with RSUs. These road side units are connected by wire. We develop a randomized algorithm to deploy road side units in the VANET. It gives an approximation to the optimal distance to guarantee the information can be passed to RSUs from the accident site via the VANET. Simulations are conducted to show the performance of our proposed method.

关键词： VANET RSU Placement randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved randomized algorithm for Square Root Extraction 1

引用

4th International Conference on Information Computing and Applications (ICICA)

作者： Liu, Lihua Cao, Zhengjun Sha, Qian Shanghai Maritime Univ Dept Math Shanghai Peoples R China

ISBN: (数字)9783642537035

ISBN: (纸本)9783642537035;9783642537028

Square root extraction plays a key role in cryptosystems based on elliptic curves. Motwani and Raghavan had proposed an algorithm for square root extraction over finite field F-p, where p is an odd prime. It is a randomized algorithm with expected running time O(len(p)(4)). Its complexity relies mainly on the loops calling Euclid's algorithm for polynomials over F-p. In this paper, we propose an improvement of it. The new algorithm calls a subroutine for computing a Legendre symbol. Since the running time of computing a Legendre symbol is much less than that of Euclid's algorithm for polynomials over F-p, the new algorithm is more efficient. It only takes time O(len(p)(3)). We also compare the new algorithm with those algorithms for square root extraction over finite fields.

关键词： Quadratic Residue Legendre Symbol randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：