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

The maximum weight perfect matching problem for complete weighted graphs is in pc

parallel algorithms and Applications 1995年第2-3期6卷 143-166页

作者： Osiakwan, Constantine N. K. Akl, Selim G. Bell Northern Research Ottawa Ontario K1Y 4H7 3500 Carling Avenue Canada Computing and Information Science Queen’s University Kingston Ontario K7L 3N6 Canada

A matching M of a graph G = (V,E) is a subset of the set of edges E such that no two edges in M are adjacent. A maximum weight (perfect) matching of a (complete) weighted graph is a (perfect) matching of the graph where the sum of the weights of the edges in the matching is maximum. There are efficient sequential algorithms that use linear programming (LP) for computing maximum weight matchings. These are primal-dual algorithms. A number of randomized parallel algorithms for maximum weight matchings have also appeared in the literature. Finding a deterministic parallel algorithm for computing maximum weight matchings in complete graphs has been an open problem for some time. Since LP is known to be P-complete, then, by the parallel computation thesis, it is unlikely that there exists an NC algorithm that uses LP to solve the maximum weight matching problem. In this paper, we present an LP-based parallel algorithm for maximum weight perfect matching in a complete weighted graph. The algorithm is designed for the EREW PRAM model of parallel computation, and runs in [formula omitted] time for p ≤ n, where p is the number of processors and n is the number of vertices in the graph. This algorithm provides an optimal speedup with respect to the O(n³) sequential LP-based solution of Gabow [18] or Lawler [28], for p ≤ n/logn. This shows that the maximum weight perfect matching problem for complete graphs is in the class of problems (known as PC*) for which an optimal speedup parallel algorithm can be designed on the PRAM using a polynomial number of processors. This is the first deterministic optimal speedup parallel algorithm designed for the maximum weight matching problem on complete graphs. © 1995, Taylor & Francis Group, LLC. All rights reserved.

关键词： Maximum weight matching Optimal speedup parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

PASSENGERS' CHOICES ON AIRPORT DROP-OFF SERVICE: A DECISION FORECAST BASED ON SOCIAL LEARNING AND MACHINE LEARNING

PASSENGERS' CHOICES ON AIRPORT DROP-OFF SERVICE: A DECISION ...

引用

2016 4th IEEE International Conference on Cloud Computing and Intelligence Systems（IEEE CCIS2016）

作者： Zhongqiang Wang Jian Peng Yu Chen Limiao Ning College of Computer Science Sichuan University

ISBN: (纸本)9781509012572

Airport drop-off service provided by airlines is a chauffeur-driven service(i.e. Uber and Di Di) as an emerging travel choice for travelers. More and more passenger enjoy the drop-off service. In practice, we find an interesting question: if a passenger has ever choice the drop-off service, whether they are willing to recommend this service to other traveler? Although the acknowledgment that social learning is related to travel decision is promoted, quantitative analysis about how social learning shape and impact the decision of passengers is still limited. We study and estimate a diffusion probability between different passengers by proposing a CCM(Co-travel Link Cascade Model) based on a modified EM iterative algorithm. Then, we segment passengers into three types(Influenced, Unchecked and Immune). The three types of passengers are predicated by approaches of IC-like model, Random Forest model and probabilistic model, respectively. In addition, we also design a parallel implementation of our proposed algorithm in the Apache Spark distributed data processing environment. Experimental results on a real aviation data set demonstrate that CCM can efficiently infer the decision of travelers.

关键词： Airport drop-off service Social influence EM algorithm Machine learning parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence properties of numerical simulation for neural networks

引用

Electronics and Communications in Japan (Part III: Fundamental Electronic Science) 1992年第5期75卷 28-35页

作者： Urahama, Kiichi Faculty of Computer Science and Electronics Kyushu Institute of Technology Iizuka 820 Japan

This paper discusses the convergence of the numerical solution of the neural network, whose stability is such that any trajectory asymptotically approaches the equilibrium solution. It is shown first that when the connection among neurons is weak, the upper limit of the step width, for which the asynchronous iteration converges, is the same as in the synchronous iteration. It is pointed out that the asynchronous method is expected to achieve a faster convergence in the parallel computer. On the other hand, when the synaptic connection is symmetrical, the asynchronous iteration does not converge in general unless the step width is set smaller than that of the synchronous iteration. It is shown also that the stiffness of the Hopfield network to solve the combinational optimization problem is enhanced with the increase of the network scale. Since the computational complexity is expected to increase rapidly in the forward Euler method, the iterative method based on the backward Euler method is proposed. It is shown that the proposed method has a better convergence property. Finally, the foregoing theoretical results are verified qualitatively through simple examples. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

关键词： asynchronous iteration convergence property Hopfield network Neural network numerical solution parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Molecular Dynamics On The Connection Machine Using Fortran

引用

Molecular Simulation 1991年第1-2期7卷 1-42页

作者： Boltjes, B. De Leeuw, S.W. Department for Physical Chemistry University of Amsterdam NL-1018 WS Amsterdam Nieuwe Achtergracht 127 Netherlands Material Science Division Argonne National Laboratory Argonne III. 60439 United States

A new algorithm for molecular dynamics on the Connection Machine is presented and compared to an algorithm known from literature. The algorithms have been in implemented in CM Fortran 8x. Their performances, measured in CPU time, are compared and discussed for the simple Lennard-Jones system and for a liquid charged particle system. The implementation and performance of the Ewald sum, used for the charged particle system, is presented and discussed. The new algorithm is suitable for use with a cut off radius. Other advantages of the algorithm are discussed. © 1991, Taylor & Francis Group, LLC. All rights reserved.

关键词： connection machine Molecular dynamics parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact solution of linear equations on distributed-memory multiprocessors

引用

parallel algorithms and Applications 1994年第1-2期3卷 135-143页

作者： Koç, Ç.K. Güvenç, A. Bakkalo Ğ Lu, B. Department of Electrical and Computer Engineering Oregon State University Corvallis OR 97331 United States

We present two new parallel algorithms for exact (error-free) solution of a system of linear equations on a distributed-memory multiprocessor. The exact solution is obtained using the congruence technique which consists of two steps: First, the system of linear equations is converted to systems of linear congruence equations with respect to several prime moduli, and each of these systems is solved on a separate processor. Then, these solutions are combined using the mixed-radix conversion algorithm to obtain the exact solution. The first step is completely (embarrassingly) parallel with no communication requirements among the processors. We improve our previous work and describe two efficient parallel algorithms for the second step. We present the results of our experiments on an Intel iPSC/860 with 8 processors. A linear system of dimension 128 with integer entries as large as 10577 is solved in about 195 seconds on 8 processors with an efficiency of 99.76%. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Congruence technique mixed-radix conversion parallel algorithm single-node and multi-node broadcast

来源：评论

学校读者我要写书评

暂无评论

Application of Fuzzy Optimization to the Orienteering Problem

引用

ADVANCES IN FUZZY SYSTEMS 2015年第1期2015卷 12-12页

作者： Verma, Madhushi Shukla, K. K. IIT BHU Dept Comp Sci & Engn Varanasi 221005 Uttar Pradesh India

This paper deals with the orienteering problem (OP) which is a combination of two well-known problems (i.e., travelling salesman problem and the knapsack problem). OP is an NP-hard problem and is useful in appropriately modeling several challenging applications. As the parameters involved in these applications cannot be measured precisely, depicting them using crisp numbers is unrealistic. Further, the decision maker may be satisfied with graded satisfaction levels of solutions, which cannot be formulated using a crisp program. To deal with the above-stated two issues, we formulate the fuzzy orienteering problem (FOP) and provide a method to solve it. Here we state the two necessary conditions of OP of maximizing the total collected score and minimizing the time taken to traverse a path (within the specified time bound) as fuzzy goals and the remaining necessary conditions as crisp constraints. Using the max-min formulation of the fuzzy sets obtained from the fuzzy goals, we calculate the fuzzy decision sets (Z and Z*) that contain the feasible paths and the desirable paths, respectively, along with the degrees to which they are acceptable. To efficiently solve large instances of FOP, we also present a parallel algorithm on CREW PRAM model.

关键词： Knapsack problem Travelling salesman problem Fuzzy Maximization parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Load Balancing, Selection and Sorting on the Star and Pancake Interconnection Networks

引用

parallel algorithms and Applications 1994年第1-2期2卷 27-42页

作者： Qiu, K. Akl, S.G. Department of Computing and Information Science Queen’s University Kingston Ontario United States

We present load balancing, selection, and sorting algorithms for the star and pancake networks. Let Xn be an n-star or n-pancake with p = n! processors with N elements distributed evenly among the processors such that... 详细信息

We present load balancing, selection, and sorting algorithms for the star and pancake networks. Let X_n be an n-star or n-pancake with p = n! processors with N elements distributed evenly among the processors such that each processor holds at most [N/p] elements, N≥ n!. Our selection algorithm selects the kth smallest element on X_n. in O((N/p)n log p + log(N/p)n⁴ log²n) time. The sorting algorithm sorts the N elements on X_n, in O((N/p)n log p + log(N/p)n⁴log²n) time. This new sorting algorithm is asymptotically faster than the previously fastest known algorithm when N = Ω((n log^2+δ n)P) = Ω((log p)(log p)^1+δp), i.e., when N = O(p^l+є), for any δ > 0 and є > 0. A main component of the sorting algorithm 1s a procedure for balancing the load among all the processors in each of the two networks. This procedure runs in O(nM + n³logn) time, where M is the maximum load among all the processors in the network. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Interconnection network Load balancing Pancake graph parallel algorithm Selection Sorting Star graph

来源：评论

学校读者我要写书评

暂无评论

Lock Bypassing: An Efficient algorithm For Concurrently Accessing Priority Heaps

引用

ACM Journal of Experimental algorithmics 1998年 3卷 3-3页

作者： Yan, Yong Zhang, Xiaodong HAL Computer Systems Inc. Campbell California 95008 United States Department of Computer Science College of William & Mary Williamsburg Virginia 23187-8795 P. O. Box 8795 United States

The heap representation of priority queues is one of the most widely used data structures in the design of parallel algorithms. Efficiently exploiting the parallelism of a priority heap has significant influence on the efficiency of a wide range of applications and parallel algorithms. In this paper, we propose an aggressive priority heap operating algorithm, called the lock bypassing algorithm (LB) on shared memory systems. This algorithm minimizes interference of concurrent enqueue and dequeue operations on priority heaps while keeping the strict priority property: a dequeue always returns the minimum of a heap. The unique idea that distinguishes the LB algorithm from previous concurrent algorithms on priority heaps is the use of locking-on-demand and lock-bypassing techniques to minimize locking granularity and to maximize parallelism. The LB algorithm allows an enqueue operation to bypass the locks along its insertion path until it reaches a possible place where it can perform the insertion. Meanwhile a dequeue operation also makes its locking range and locking period as small as possible by carefully tuning its execution procedure. The LB algorithm is shown to be correct in terms of deadlock freedom and heap consistency. The performance of the LB algorithm was evaluated analytically and experimentally in comparison with previous algorithms. Analytical results show that the LB algorithm reduces by half the number of locks waited for in the worst case by previous algorithms. The experimental results show that the LB algorithm outperforms previously designed algorithms by up to a factor of 2 in hold time. © 1998, ACM. All rights reserved.

关键词： Aggressive Locking parallel algorithm Performance Evaluation Priority Heap Shared-memory System

来源：评论

学校读者我要写书评

暂无评论

The Optimal Location of a Structured Facility in a Tree Network

引用

parallel algorithms and Applications 1994年第1-2期2卷 43-60页

作者： Peng, Shietung Lo, Win-Tsung School of Computer Science and Engineering The University of Aizu Aizu-wakamatsu Fukushima Japan Computer Science Department University of Maryland Baltimore MD 21228 United States

Efficient parallel algorithms for finding an optimal path-shaped or tree-shaped facility with a specified size in a tree network are presented. Four kinds of optimization criteria are considered: Minimizing/maximizing distancesum/eccentricity. There are eight cases when considering facility shapes and optimization criteria. parallel algorithms for finding a minimum/maximum distancesum path were presented in [9]. The other six cases are studied in this paper. Two of these six cases can be solved optimally in linear Time x Processor complexity. For the problem of finding a maximum distancesum tree, the algorithm presented in this paper is the first polynomial time solution under a reasonable assumption. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Distancesum Eccentricity Location theory parallel algorithm Tree contraction. EREW PRAM Tree network

来源：评论

学校读者我要写书评

暂无评论

parallel FINITE ELEMENT LAPLACE TRANSFORM METHOD FOR THE NON-EQUILIBRIUM GROUNDWATER TRANSPORT EQUATION

引用

International Journal for Numerical Methods in Engineering 1998年第14期40卷

作者： GIORGIO PINI MARIO PUTTI Dip. di Metodi e Modelli Matematici per le Scienze Applicate Università degli studi di Padova via Belzoni 7 35131 Padova Italy

Groundwater transport of contaminants undergoing rate-limited or non-equilibrium sorption onto the solid matrix is often described by the dual-porosity or two-domain model, whereby the rate-limited reaction occurs between a mobile and an immobile region. When the sorption reaction is represented by a first-order kinetic relationship, the equation takes the form of a convection–dispersion partial differential equation with an integral term describing the mass transfer between the two regions. An efficient solution algorithm for this type of problems consists in the transformation of the original equation into the Laplace space and subsequent numerical solution of the resulting steady-state equation in the complex space. The exploitation of the Laplace transform to solve the time dependency restricts the application of the technique to linear advection and dispersion terms, while non-linear reactions can be accommodated in particular cases only. This approach has the advantage that it is easily parallelizable, and is therefore proposed in this paper as an efficient algorithm for the parallelization in time of these types of integrodifferential equations. The parallel efficiency of PFELT has been tested on a Cray T3D parallel computer for three sample problems of size N =1071, 3721, and 15 275, respectively, where N is the number of nodal mesh points. The speed-ups obtained vary from 1·98, with two processors, to 39·93 with 64 processors, for the most favorable case. This corresponds to a percentage of parallel work greater than 98 per cent, and a parallel efficiency of more than 60 per cent in the best case, showing the good performance achievable with this algorithm. © 1997 John Wiley & Sons, Ltd.

关键词： groundwater transport non-equilibrium sorption Laplace transformation finite element parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：