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

EXPECTED-TIME COMPLEXITY RESULTS FOR HIERARCHIC CLUSTERING algorithms WHICH USE CLUSTER CENTERS

INFORMATION PROCESSING LETTERS 1983年第5期16卷 237-241页

作者： MURTAGH, F Department of Computer Science University College Dublin Dublin 4 Ireland

Hierarchic clustering algorithms are being used for structuring and interpreting data; however, their practical use hinges on fast algorithms for implementing them. Although such algorithms exist, they suffer from 2 disadvantages - the ''chaining'' effect and the lack of a natural definition of ''cluster representative'' or cluster center. Widely used clustering methods that do not suffer from this 2nd disadvantage are the median method, the centroid method, and Ward's minimum variance method. Some recent algorithmic improvements in these methods have succeeded in making them computationally more efficient and of greater practical interest. These results are extended through the examination of fast expected-time results. For the median and centroid methods, where the cardinality of clusters is not used in the definition of dissimilarity between cluster centers, the expected-time performance is O(N). The expected time complexity of Ward's method is upper-bounded by O(N log N).

关键词： probabilistic algorithms dynamic searching nearest neighbours

来源：评论

学校读者我要写书评

暂无评论

A NEW ALGORITHM FOR FACTORING POLYNOMIALS OVER FINITE-FIELDS

引用

MATHEMATICS OF COMPUTATION 1981年第154期36卷 587-592页

作者： CANTOR, DG ZASSENHAUS, H OHIO STATE UNIV DEPT MATHCOLUMBUSOH 43210

Abstract: We present a new probabilistic algorithm for factoring polynomials over finite fields.

关键词： Factoring polynomials finite fields probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast computation of the Smith form of a sparse integer matrix

引用

COMPUTATIONAL COMPLEXITY 2001年第1期10卷 41-69页

作者： Giesbrecht, M Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix A is an element of Z(m*n). The algorithm treats A as a "black box"-A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about O(m(2) log parallel toAparallel to) black box evaluations w Aw mod p for word-sized primes p and w is an element of Z(p)(n*1), plus O(m(2) n log parallel toAparallel to + m(3) log(2) parallel toAparallel to) additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no "fill-in" or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about O(n . MM(m) log parallel toAparallel to + m(3) log(2) parallel toAparallel to) bit operations, where O(MM(m)) operations are sufficient to multiply two m x m matrices over a field. Both algorithms are probabilistic of the Monte Carlo type-on any input they return the correct answer with a controllable, exponentially small probability of error.

关键词： sparse integer matrix Smith form probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

A SUCCESSFUL ALGORITHM FOR THE UNDIRECTED HAMILTONIAN PATH PROBLEM

引用

DISCRETE APPLIED MATHEMATICS 1985年第2期10卷 179-195页

作者： THOMPSON, GL SINGHAL, S Management Science Research Group Graduate School of Industrial Administration Garnegie-Mellon University Pittsburgh PA 15213 USA

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given. It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported. Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.

关键词： Hamiltonian Paths Hamiltonian Cycles ramification index heuristic probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast computation of a rational point of a variety over a finite field

引用

MATHEMATICS OF COMPUTATION 2006年第256期75卷 2049-2085页

作者： Cafure, Antonio Matera, Guillermo Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat RA-1428 Buenos Aires DF Argentina Univ Nacl Gen Sarmiento Inst Desarrollo Humano RA-1613 Buenos Aires DF Argentina

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bezout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

关键词： varieties over finite fields rational points geometric solutions straight-line programs probabilistic algorithms first Bertini theorem

来源：评论

学校读者我要写书评

暂无评论

Using parallel & distributed computing for real-time solving of vehicle routing problems with stochastic demands

引用

ANNALS OF OPERATIONS RESEARCH 2013年第1期207卷 43-65页

作者： Juan, Angel A. Faulin, Javier Jorba, Josep Caceres, Jose Manuel Marques, Joan Open Univ Catalonia Dept Comp Sci Multimedia & Telecommun Barcelona 08018 Spain Univ Publ Navarra Dept Stat & OR Pamplona 31006 Spain

This paper focuses on the Vehicle Routing Problem with Stochastic Demands (VRPSD) and discusses how Parallel and Distributed Computing Systems can be employed to efficiently solve the VRPSD. Our approach deals with uncertainty in the customer demands by considering safety stocks, i.e. when designing the routes, part of the vehicle capacity is reserved to deal with potential emergency situations caused by unexpected demands. Thus, for a given VRPSD instance, our algorithm considers different levels of safety stocks. For each of these levels, a different scenario is defined. Then, the algorithm solves each scenario by integrating Monte Carlo simulation inside a heuristic-randomization process. This way, expected variable costs due to route failures can be naturally estimated even when customers' demands follow a non-normal probability distribution. Use of parallelization strategies is then considered to run multiple instances of the algorithm in a concurrent way. The resulting concurrent solutions are then compared and the one with the minimum total costs is selected. Two numerical experiments allow analyzing the algorithm's performance under different parallelization schemas.

关键词： Vehicle routing problem with stochastic demands Parallel and distributed computing Monte Carlo simulation probabilistic algorithms Heuristics

来源：评论

学校读者我要写书评

暂无评论

On the finite-time dynamics of ant colony optimization

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2006年第1期8卷 105-133页

作者： Gutjahr, Walter J. Univ Vienna Dept Stat & Decis Support Syst Vienna Austria

An analytical framework for investigating the finite-time dynamics of ant colony optimization (ACO) under a fitness-proportional pheromone update rule on arbitrary construction graphs is developed. A limit theorem on the approximation of the stochastic ACO process by a deterministic process is demonstrated, and a system of ordinary differential equations governing the process dynamics is identified. As an example for the application of the presented theory, the behavior of ACO on three different construction graphs for subset selection problems is analyzed and compared for some basic test functions. The theory enables first rough theoretical predictions of the convergence speed of ACO.

关键词： ant colony optimization convergence speed probabilistic algorithms stochastic approximation stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

On the energy balance problem in distributed sensor networks

引用

COMPUTER SCIENCE REVIEW 2010年第2期4卷 65-79页

作者： Nikoletseas, Sotiris Univ Patras Comp Technol Inst Patras Greece

We investigate the problem of how to achieve energy balanced data propagation in distributed wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, throughout the execution of the data propagation protocol. This property is crucial for prolonging the network lifetime, by avoiding early energy depletion of sensors. We survey representative solutions from the state of the art. We first present a basic algorithm that in each step probabilistically decides whether to propagate data one-hop towards the final destination (the sink), or to send it directly to the sink. This randomized choice trades-off the (cheap, but slow) one-hop transmissions with the direct transmissions to the sink, which are more expensive but bypass the bottleneck region around the sink and propagate data fast. By a detailed analysis using properties of stochastic processes and recurrence relations we precisely estimate (even in closed form) the probability for each propagation option necessary for energy balance. The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy balanced, is also energy efficient. We then enhance this basic result by surveying some recent findings including a generalized algorithm and demonstrating the optimality of this two-way probabilistic data propagation, as well as providing formal proofs of the energy optimality of the energy balance property. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Distributed computing Sensor networks Energy efficiency Routing probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Elliptic periods and primality proving

引用

JOURNAL OF NUMBER THEORY 2013年第1期133卷 343-368页

作者： Ezome, Tony Lercier, Reynald DGA MI F-35174 La Roche Marguerite Bruz France Univ Sci & Tech Masuku Fac Sci Dept Math & Informat Franceville Gabon Univ Rennes 1 Inst Rech Math Rennes F-35042 Rennes France

We construct extension rings with fast arithmetic using isogenies between elliptic curves. As an application, we give an elliptic version of the AKS primality criterion. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Elliptic curve Primality Galois theory probabilistic algorithms Ring theory

来源：评论

学校读者我要写书评

暂无评论

REASONING ABOUT probabilistic PARALLEL PROGRAMS

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1994年第3期16卷 798-842页

作者： RAO, JR IBM Thomas J. Watson Research Center Yorktown Heights NY

The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1. We present a proof methodology based on existing proof systems for probabilistic algorithms, the theory of the predicate transformer, and the theory of UNITY. Although the proofs of probabilistic programs are slippery at best, we show that such programs can be derived with the same rigor and elegance that we have seen in the derivation of sequential and parallel programs. By applying this methodology to derive probabilistic programs, we hope to develop tools and techniques that would make randomization a useful paradigm in algorithm design.

关键词： algorithms VERIFICATION CORRECTNESS PROOFS PARALLEL PROGRAMMING probabilistic algorithms PROGRAMMING METHODOLOGY SPECIFICATION TECHNIQUES VERIFICATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：