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

AN OPTIMAL randomized PARALLEL algorithm FOR FINDING CONNECTED COMPONENTS IN A GRAPH

SIAM JOURNAL ON COMPUTING 1991年第6期20卷 1046-1067页

作者： GAZIT, H Duke Univ Durham NC United States

A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of T = O(log(n)) with P = O((m + n)/log(n)) processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product P . T is a linear function of the input size. The algorithm requires O(m + n) space, which is the input size, so it is optimal in space as well.

关键词： CONNECTED COMPONENTS randomized algorithm PARALLEL COMPUTING CRCW UNDIRECTED GRAPH

来源：评论

学校读者我要写书评

暂无评论

A randomized-algorithm-based decomposition-ensemble learning methodology for energy price forecasting

引用

ENERGY 2018年 157卷 526-538页

作者： Tang, Ling Wu, Yao Yu, Lean Beihang Univ Sch Econ & Management Beijing 100191 Peoples R China Beijing Univ Chem Technol Sch Econ & Management Beijing 100029 Peoples R China

Inspired by the interesting idea of randomization, some powerful but time-consuming decomposition-ensemble learning paradigms can be extended into extremely efficient and fast variants by using randomized algorithms as individual forecasting tools. In the proposed methodology, Three major steps, (1) data decomposition via ensemble empirical mode decomposition, (2) individual prediction via a randomized algorithm (using randomization to mitigate training time and parameter sensitivity), and (3) results ensemble to produce final prediction, are included. Different from other existing decomposition-ensemble models using traditional econometric approaches or computational intelligence methods in individual prediction, this study employs some emerging randomized algorithms-extreme learning machine, random vector functional link network (using randomly fixed weights and bias in neural networks), and random kitchen sinks (using randomly mapping features to approximate kernels)-to dramatically save computational time and enhance prediction accuracy. With the Brent oil prices and the Henry Hub natural gas prices as studying samples, the empirical study statistically confirms that the proposed randomized-algorithm-based decomposition-ensemble learning models are proved to be excellently efficient and fast, relative to popular single techniques (including computational intelligence methods and randomized algorithms) and similar decomposition-ensemble counterparts (using the aforementioned single techniques as individual forecasting tools). (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Decomposition-ensemble learning methodology randomized algorithm Energy price forecasting Extreme learning machine Random vector functional link network Random kitchen sinks

来源：评论

学校读者我要写书评

暂无评论

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卷

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：