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

UET SCHEDULING WITH UNIT INTERPROCESSOR COMMUNICATION DELAYS

DISCRETE APPLIED MATHEMATICS 1987年第1期18卷 55-71页

作者： RAYWARDSMITH, VJ School of Information Systems University of East Anglia Norwich NR4 7TJ UK

We consider the problem of scheduling a partially ordered set of unit execution time (UET) tasks on m > 1 processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, ω c g satisfies w c g 3− 2 m w c opt − 1− 1 m where ω c opt is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behavour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.

关键词： UET scheduling list scheduling communication delays multiprocessor systems algorithm analysis NP-completeness speed-up anomaly

来源：评论

学校读者我要写书评

暂无评论

On the variance of the internal path length of generalized digital trees - The Mellin convolution approach

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期242卷 143-168页

作者： Hubalek, F Univ Vienna Inst Stat A-1210 Vienna Austria

This paper studies a generalization of the internal path length of a random digital search tree to bucket trees, which are capable of storing up to b records per node. We show that under the assumption of the symmetric Bernoulli probabilistic model the expected path length of a tree built from N records is asymptotically Nlog(2)N + (A + delta(1)(log(2)N))N and the variance is (C + epsilon(1)(log(2)N))N, where A and C depend on b only. The continuous functions delta(1) and epsilon(1) are periodic with mean 0 and period 1. The proof's are analytical and make use of generating functions, harmonic sums and the Mellin integral transform. An important and very general tool for the analysis is Mellin's convolution integral. These results and techniques are motivated by a paper by Flajolet and Richmond and by Kirschenhofer, Prodinger, and Szpankowski. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： digital search trees algorithm analysis mellin transform

来源：评论

学校读者我要写书评

暂无评论

A NEW APPROACH FOR THE DOMINATION PROBLEM ON PERMUTATION GRAPHS

引用

INFORMATION PROCESSING LETTERS 1991年第4期37卷 219-224页

作者： LIANG, Y RHEE, C DHALL, SK LAKSHMIVARAHAN, S Parallel Process. Inst. Sch. Electr. Eng. and Comp. Sci. Univ. Oklahoma Norman OK 73019 USA

Farber and Keil presented an O(n3) algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O(n(m + n)) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.

关键词： algorithm analysis MINIMUM WEIGHT DOMINATING SET PERMUTATION GRAPH

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the reduce-scatter operation in LogGP

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第9期8卷 970-982页

作者： Iannello, G Dipartimento di Informatica e Sistemistica Università di Napoli Federico II Napoli Italy

We consider the problem of efficiently performing a reduce-scatter operation in a message passing system. Reduce-scatter is the composition of an element-wise reduction on vectors of n elements initially held by n processors, with a scatter of the resulting vector among the processors. In this paper, we present two algorithms for the reduce-scatter operation, designed in LogGP. The first algorithm assumes an associative and commutative reduction operator and it is optimal in LogGP within a small constant factor. The second algorithm allows the reduction operator to be noncommutative, and it is asymptotically optimal when values to be combined are large arrays. To achieve these results, we developed a complete analysis of both algorithms in LogGP, including the derivation of lower bounds for the reduce-scatter operation, and the study of the m-item version of the problem, i.e., the case when the initial elements are vectors themselves. Reduce-scatter has been included as a collective operation in the MPI standard message passing library, and can be used, for instance, in parallel matrix-vector multiply when the matrix is decomposed by columns. To model a message passing system, we adopted the LogGP model, an extension of LogP that allows the modeling of messages of different length. While this choice makes the analysis somewhat more complex, it leads to more realistic results in the case of gather/scatter algorithms.

关键词： reduce-scatter algorithm analysis parallel algorithm collective communication operations LogP LogGP postal model generalized Fibonacci numbers MPI

来源：评论

学校读者我要写书评

暂无评论

The complete solution of the competitive rank selection problem

引用

algorithmICA 1998年第4期22卷 413-447页

作者： Bruss, FT Drmota, M Louchard, G Free Univ Brussels Dept Math B-1050 Brussels Belgium Free Univ Brussels ISRO B-1050 Brussels Belgium Vienna Tech Univ Dept Discrete Math A-1040 Vienna Austria Free Univ Brussels Dept Informat B-1050 Brussels Belgium

Two decision-makers A and B observe sequentially a given permutation of n uniquely rankable options. A and B have one choice each (without recall) and both must make a choice. At each step only the relative ranks are known, and A has the priority of choice. At the end the (absolute) ranks are compared and the winner is the one who has chosen the better rank. Extending results by Enns and Ferenstein [6] and Berry et al. [1] this article gives, for both A and B, the optimal strategy and the corresponding winning probabilities. We show in particular that the limiting winning probabilities for A and B do exist, which closes a most important gap in the work of previous authors. This also provides an algorithm for numerically computing the limiting value of these probabilities. Although our proof is analytic in a strong sense, it is interesting to see that it would have been very hard to assemble it without the help of computer algebra. The reason is that the functions we have to investigate display subranges of indices which contrast considerably with respect to error terms when certain terms are replaced by approximations, and that computations were very helpful to locate those ranges where a particularly fine tuning of error estimates turned out to be indispensable.

关键词： competitive secretary problem no-information case relative ranks recursive sequences convergence of recursive solutions algorithm analysis discrepancy problems minimax optimal Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Average-case performance of the Apriori algorithm

引用

SIAM JOURNAL ON COMPUTING 2004年第5期33卷 1223-1260页

作者： Purdom, PW Van Gucht, D Groth, DP Indiana Univ Dept Comp Sci Bloomington IN 47405 USA Indiana Univ Sch Informat Bloomington IN 47405 USA

The failure rate of the Apriori algorithm is studied analytically for the case of random shoppers. The time needed by the Apriori algorithm is determined by the number of item sets that are output (successes: item sets that occur in at least k baskets) and the number of item sets that are counted but not output (failures: item sets where all subsets of the item set occur in at least k baskets but the full set occurs in less than k baskets). The number of successes is a property of the data;no algorithm that is required to output each success can avoid doing work associated with the successes. The number of failures is a property of both the algorithm and the data. We find that under a wide range of conditions the performance of the Apriori algorithm is almost as bad as is permitted under sophisticated worst-case analyses. In particular, there is usually a bad level with two properties: (1) it is the level where nearly all of the work is done, and (2) nearly all item sets counted are failures. Let l be the level with the most successes, and let the number of successes on level l be approximately ((m)(l)) for some m. Then, typically, the Apriori algorithm has total output proportional to approximately ((m)(l)) and total work proportional to approximately ((m)(l+1)). In addition m is usually much larger than l, so the ratio of work to output is proportional to approximately m/(l+1). The analytical results for random shoppers are compared against measurements for three data sets. These data sets are more like the usual applications of the algorithm. In particular, the buying patterns of the various shoppers are highly correlated. For most thresholds, these data sets also have a bad level. Thus, under most conditions nearly all of the work done by the Apriori algorithm consists in counting item sets that fail.

关键词： data mining algorithm analysis Apriori algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient algorithm for the Shortest Vector Problem

引用

IEEE ACCESS 2018年 6卷 61478-61487页

作者： Chuang, Yu-Lun Fan, Chun-, I Tseng, Yi-Fan Natl Sun Yat Sen Univ Dept Comp Sci & Engn Kaohsiung 81424 Taiwan Natl Sun Yat Sen Univ Informat Secur Res Ctr Kaohsiung 80424 Taiwan Natl Sun Yat Sen Univ Intelligent Elect Commerce Res Ctr Kaohsiung 80424 Taiwan

Lattice is widely used in cryptography since it has potential for defending quantum attacks. One of the significant problems in such cryptography is the shortest vector problem (SVP). This problem is to find the non-zero shortest vector in lattice. The SVP is an NP-hard problem under randomized reductions proven by Ajtai, and many cryptosystems are secure under the assumption that SVP is hard, such as NTRU. On the other hand, some primitives of lattice-based cryptography require relatively short vectors. In this paper, we propose a new SVP algorithm that can be performed in time complexity O(n(3)). We also prove that the Hermite factor of the proposed algorithm is polynomial-bounded.

关键词： Shortest vector problem algorithm analysis optimization theory lattice lattice-based cryptography

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for an electronic commerce money distribution system

引用

algorithmICA 2002年第3期33卷 287-299页

作者： Kawazoe, H Shibuya, T Tokuyama, T IBM Japan Ltd Ind eApplicat Sales eBusiness Solut Chuo Ku Tokyo 1038510 Japan Tokyo Res Lab IBM Res Div Yamato Kanagawa 2428502 Japan Tohoku Univ Grad Sch Informat Sci Aoba Ku Sendai Miyagi 9808577 Japan

We consider the money distribution problem for a micro-payment scheme using a distributed server system: in particular, for an automatic charging scheme named PayPerClick that allows Internet users to view Web pages for which access charges are levied without tedious payment procedures. A major bottleneck in the scheme is the network traffic caused by the distribution of electronic money to many different servers. We propose a simple online algorithm for distributing electronic money to servers, so that the network traffic is minimized. The algorithm achieves the optimal online competitive ratio. We also consider a weighted version, for which we give an asymptotically optimal online algorithm within a constant factor.

关键词： online algorithm algorithm analysis electronic commerce money distribution system PayPerClick

来源：评论

学校读者我要写书评

暂无评论

A model to simplify 2D triangle meshes with irregular shapes

引用

APPLIED MATHEMATICS AND COMPUTATION 2010年第10期216卷 2937-2946页

作者： Tortosa, L. Vicent, J. F. Zamora, A. Univ Alicante Dept Ciencia Computac & Inteligencia Artificial E-03080 Alicante Spain

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape. (C) 2010 Elsevier Inc. All rights reserved.

关键词： algorithm analysis Mesh simplifications Artificial neural networks Triangulation GNG3D model Self-organizing systems

来源：评论

学校读者我要写书评

暂无评论

Further results on an abstract model for branching and its application to mixed integer programming

引用

MATHEMATICAL PROGRAMMING 2021年第1-2期190卷 811-841页

作者： Anderson, Daniel Le Bodic, Pierre Morgan, Kerri Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA Monash Univ Fac Informat Technol Caulfield Australia Deakin Univ Fac Sci Engn & Built Environm Sch Informat Technol Geelong Vic Australia

A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection can affect the size of the resulting search trees by orders of magnitude. A recent article by Le Bodic and Nemhauser (Math Program 166(1-2):369-405, 2017) investigated variable selection rules by developing a theoretical model of B&B trees from which they developed some new, effective scoring functions for MIP solvers. In their work, Le Bodic and Nemhauser left several open theoretical problems, solutions to which could guide the future design of variable selection rules. In this article, we first solve many of these open theoretical problems. We then implement an improved version of the model-based branching rules in SCIP 6.0, a state-of-the-art academic MIP solver, in which we observe an 11% geometric average time and node reduction on instances of the MIPLIB 2017 Benchmark Set that require large B&B trees.

关键词： Branch and bound Mixed-integer programming algorithm analysis Branching rules

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：