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

A FAST AND SIMPLE randomized PARALLEL algorithm FOR MAXIMAL MATCHING

INFORMATION PROCESSING LETTERS 1986年第2期22卷 77-80页

作者： ISRAELI, A ITAI, A TECHNION ISRAEL INST TECHNOL DEPT COMP SCIIL-32000 HAIFAISRAEL

A simple parallel randomized algorithm to find a maximal matching is developed. It is randomized in that it uses randomly chosen numbers. Its characteristics and efficiency do not depend upon the assumption that the input graph is random. A basic operation of the algorithm is a random choice operation (RCO) involving a nonzero boolean vector. The expected time complexity of the algorithm is proven, leading to a trivial implementation of the algorithm on an EREW-PRAM. It is then shown how to perform RCO in the expected time on a CRCW-PRAM, which yields the promised complexity. The expected time is independent of the input graph's structure; this improves the best known deterministic algorithm.

关键词： Maximal matching parallel algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized OPTIMAL algorithm FOR SLOPE SELECTION

引用

INFORMATION PROCESSING LETTERS 1991年第4期39卷 183-187页

作者： MATOUSEK, J Department of Applied Mathematics Charles University Malostranské nám. 25 118 00 Praha I Czechoslovakia

Given n points in the plane and an integer k, 1 less-than-or-equal-to k less-than-or-equal-to (2n), we want to select the pair of points determining the line with the kth smallest slope. An optimal O(n log n) deterministic algorithm for this problem was given by Cole, Salowe, Steiger and Szemeredi;their algorithm is quite involved. Here we give a very simple randomized algorithm with O(n log n) expected running time. We also outline other possible applications of the technique.

关键词： COMPUTATIONAL COMPLEXITY COMPUTATIONAL GEOMETRY randomized algorithm PARAMETRIC SEARCH ORDER STATISTICS

来源：评论

学校读者我要写书评

暂无评论

qPMS10: A randomized algorithm for Efficiently Solving Quorum Planted Motif Search Problem

qPMS10: A Randomized Algorithm for Efficiently Solving Quoru...

引用

IEEE International Conference on Bioinformatics and Biomedicine

作者： Peng Xiao Soumitra Pal Sanguthevar Rajasekaran Computer Science and Engineering University of Connecticut 371 Fairfield Road Storrs CT 06269 USA

ISBN: (纸本)9781509016129

Discovering patterns in biological sequences is very important to extract useful information from them. Motifs are crucial patterns that have numerous applications including the identification of transcription factors and their binding sites, composite regulatory patterns, similiarity between families of proteins, etc. Several models of motifs have been proposed in the literature. The (l,d)-motif model is one of these that has been studied widely. The (l,d)-motif search problem is also known as Planted Motif Search (PMS). The general problem of PMS has been proven to be NP-hard. In this paper, we present an elegant as well as efficient randomized algorithm, named qPMS10, to solve PMS. Currently, the best known algorithm for solving PMS is qPMS9 and it can solve challenging (l, d)-motif instances up to (28,12) and (30,13). qPMS9 is a deterministic algorithm. We provide a performance comparison of qPMS10 with qPMS9 on standard benchmark datasets. Both theoretical and empirical analysis demonstrate that our randomized algorithm outperforms the exsiting algorithms for solving PMS. Besides, the random sampling techniques we employ in our algorithm can also be extended to solve other motif search problems including Simple Motif Search (SMS) and Edit-distance based Motif Search (EMS). Furthermore, our algorithm can be parallelized efficiently and has the potential of yielding great speedups on multi-core machines.

关键词： EMS SMS randomized algorithm randomized algorithms Synchronous meteorological satellites SMS gene Energy management systems European Monetary Union Pavement management system Premenstrual Syndrome Transcription Factors core machine deterministic algorithms standardized benchmark

来源：评论

学校读者我要写书评

暂无评论

A randomized Kaczmarz algorithm with Exponential Convergence

引用

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS 2009年第2期15卷 262-278页

作者： Strohmer, Thomas Vershynin, Roman Univ Calif Davis Dept Math Davis CA 95616 USA

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.

关键词： Kaczmarz algorithm randomized algorithm Random matrix Convergence rate

来源：评论

学校读者我要写书评

暂无评论

An optimal randomized parallel algorithm for the single function coarsest partition problem

引用

Parallel Processing Letters 1996年第2期6卷 187-193页

作者： Jájá, Joseph Institute for Advanced Computer Studies Department of Electrical Engineering University of Maryland College Park MD 20742 United States

We describe a randomized parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n) operations with high probability on the Priority CRCW PRAM. The previous best known algorithms run in O(log² n) time using O(n log²n) operations on the CREW PRAM and O(log n) time using O(n log log n) operations on the Arbitrary CRCW PRAM. The technique presented can be used to generate the Euler tour of a rooted tree optimally from the parent representation. Keywords: Coarsest partition, parallel algorithms, PRAM, randomized algorithm. © World Scientific Publishing Company.

关键词： Coarsest partition parallel algorithms PRAM randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

RaSMaLai: A randomized Switching algorithm for Maximizing Lifetime in Tree-based Wireless Sensor Networks

RaSMaLai: A Randomized Switching Algorithm for Maximizing Li...

引用

32nd IEEE INFOCOM Conference

作者： Imon, Sk Kajal Arefin Khan, Adnan Di Francesco, Mario Das, Sajal K. Univ Texas Arlington Ctr Res Wireless Mobil & Networking Arlington TX 76019 USA

ISBN: (纸本)9781467359467

In most wireless sensor network (WSN) applications, data are typically gathered by the sensor nodes and reported to a data collection point, called the sink. In order to support such data collection, a tree structure rooted at the sink is usually defined. Based on different aspects, including the actual WSN topology and the available energy budget, the energy consumption of nodes belonging to different paths in the data collection tree may vary significantly. This affects the overall network lifetime, defined in terms of when the first node in the network runs out of energy. In this paper, we address the problem of lifetime maximization of WSNs in the context of data collection trees. In particular, we propose a novel and efficient algorithm, called randomized Switching for Maximizing Lifetime (RaSMaLai) that aims at maximizing the lifetime of WSNs through load balancing with a low time complexity. We further design a distributed version of our algorithm, called D-RaSMaLai. Simulation results show that both the proposed algorithms outperform several existing approaches in terms of network lifetime. Moreover, RaSMaLai offers lower time complexity while the distributed version, D-RaSMaLai, is very efficient in terms of energy expenditure.

关键词： Sensor Networks Load Balancing Data Collection Tree Network Lifetime randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Simple Predicate to Expedite the Termination of a randomized Consensus algorithm 29

A Simple Predicate to Expedite the Termination of a Randomiz...

引用

IEEE 29th International Conference on Advanced Information Networking and Applications (IEEE AINA)

作者： Raynal, Michel Univ Rennes 1 Inst Univ France Campus Beaulieu F-35042 Rennes France Univ Rennes 1 IRISA F-35042 Rennes France

ISBN: (纸本)9781479979042

Consensus is one of the most important problems encountered in fault-tolerant distributed computing. Basically, consensus allows processes to agree on a common value. Unfortunately, no deterministic algorithm can solve this problem in an asynchronous message-passing system prone to process crash failures. One way to circumvent this impossibility, consists in enriching the system with random numbers and design a randomized algorithm. This paper considers such a consensus algorithm and presents a simple predicate that allows to expedite its termination.

关键词： Asynchronous distributed system Consensus Message-passing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized scheduling algorithm for input-queued switches

引用

Journal of Southeast University(English Edition) 2005年第1期21卷 6-10页

作者：吴俊罗军舟东南大学计算机科学与工程系南京210096

The sampling problem for input-queued (IQ) randomized scheduling algorithms is *** observe that if the current scheduling decision is a maximum weighted matching (MWM),the MWM for the next slot mostly falls in those matchings whose weight is closed to the current *** this heuristic,a novel randomized algorithm for IQ scheduling,named genetic algorithm-like scheduling algorithm (GALSA),is *** strategy is used for choosing sampling points in *** works with only O(N) samples which means that GALSA has lower complexity than the famous randomized scheduling algorithm,*** results show that the delay performance of GALSA is quite competitive with respect to that of APSARA.

关键词： switches input-queued randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A randomized SCHEDULING algorithm FOR MULTIPROCESSOR ENVIRONMENTS

引用

PARALLEL PROCESSING LETTERS 2012年第4期22卷 1250015-1250015页

作者： Mishra, Pramod Kumar Mishra, Kamal Sheel Mishra, Abhishek Tripathi, Anil Kumar Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Comp Sci Varanasi 221005 Uttar Pradesh India Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Sci & Technol Varanasi 221005 Uttar Pradesh India Sch Management Sci Khushipur Varanasi 221011 Uttar Pradesh India Indian Inst Technol Rajasthan Ctr Excellence Informat & Commun Technol Jodhpur 342011 Rajasthan India Indian Inst Technol Banaras Hindu Univ Dept Comp Engn Varanasi 221005 Uttar Pradesh India

In this paper, we propose a randomized scheduling algorithm on a fully connected homogeneous multiprocessor environment. This is a randomized version of our earlier algorithm in which we used priority of modules that was dependent on the computation and the communication times associated with the modules. First we propose a generalization of our earlier scheduling algorithm with restricted number of clusters to reduce the time complexity. Then we apply randomization to the generalized algorithm and demonstrate its superiority over our previous work. We show the complexity of our proposed algorithm as O(ab vertical bar V vertical bar(vertical bar V vertical bar+vertical bar E vertical bar)log(vertical bar V vertical bar + vertical bar E vertical bar). Here a is the number of randomization steps, and b is a limit on the number of clusters formed. If we use a and b as constants, then this gives a better complexity in comparison with the complexity of our previous algorithm that was O(vertical bar V vertical bar (2)(vertical bar V vertical bar + vertical bar E vertical bar)log(vertical bar V vertical bar+vertical bar E vertical bar)). In comparison with our previous work we get a performance improvement of up to 6.63%;and a performance improvement of up to 12.56% when compared with Sarkar's Edge Zeroing algorithm.

关键词： Clustering distributed computing homogeneous systems randomized algorithm task allocation

来源：评论

学校读者我要写书评

暂无评论

A randomized Scheduling algorithm for Multiprocessor Environments Using Local Search

引用

PARALLEL PROCESSING LETTERS 2016年第1期26卷 1650002-1650002页

作者： Mishra, Abhishek Mishra, Pramod Kurnar Birla Inst Technol & Sci Pilani Dept Comp Sci & Informat Syst Pilani 333031 Rajasthan India Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Comp Sci Varanasi 221005 Uttar Pradesh India Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Sci & Technol Varanasi 221005 Uttar Pradesh India

The LOCAL(A, B) randomized task scheduling algorithm is proposed for fully connected multiprocessors. It combines two given task scheduling algorithms (A, and B) using local neighborhood search to give a hybrid of the two given algorithms. Objective is to show that such type of hybridization can give much better performance results in terms of parallel execution times. Two task scheduling algorithms are selected: DSC (Dominant Sequence Clustering as algorithms A), and CF'F'S (Cluster Pair Priority Scheduling as algorithm B) and a hybrid is created (the LOCAL(DSC, CPPS) or simply the LOCAL task scheduling algorithm). The LOCAL task scheduling algorithm has time complexity 0(broken vertical bar V broken vertical bar broken vertical bar 1E broken vertical bar(vertical bar V broken vertical bar + broken vertical bar E broken vertical bar)), where V is the set of vertices, and P is the set of edges in the task graph. The LOCAL task scheduling algorithm is compared with six other algorithms: CF'F'S, DCCL ((Dynamic Computation. Communication Load), DSC, EZ (Edge Zeroing),. (Linear Clustering), and RDCC (randomized Dynamic Computation Comm,unicalion). Performance evaluation of the I OC AL task scheduling algorithm shows that it gives up to 80.47 C improvement of NSL (Normalized Schedule Length) over other algorithms.

关键词： Clustering distributed computing homogeneous systems local search randomized algorithm scheduling task allocation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：