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

THE COMPLEXITY OF PREEMPTIVE SCHEDULING GIVEN INTERPROCESSOR COMMUNICATION DELAYS

INFORMATION PROCESSING LETTERS 1987年第2期25卷 123-125页

作者： RAYWARDSMITH, VJ Sch. Inf. Syst. Univ. East Anglia Norwich NR4 7TJ UK

An examination is made of the problem of scheduling a set of independent tasks on a given number of identical processors. Preemption is allowed, but a communication delay is assumed. Whenever a task is preempted from one processor to another, there has to be a delay of at least k time units. It is demonstrated that, if k is equal to one, an optimal schedule can be found in polynomial time but if k is greater than or equal to 2, the corresponding decision problem is NP-complete. It is very unlikely that there is a polynomial time algorithm to find an optimal k-delay schedule for the general case. Of course, this does not mean that no such algorithm exists for special cases. However, for the more general situation, suitable heuristics will be required.

关键词： Preemptive scheduling communication delay multiprocessor system NP-completeness algorithm analysis heuristic programming

来源：评论

学校读者我要写书评

暂无评论

Trees and jumps and real roots

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2004年第1期162卷 51-55页

作者： Krandick, W Drexel Univ Dept Comp Sci Philadelphia PA 19104 USA

When the nodes of a tree are visited in depth-first order there areoccasional jumps from a deeper level of the tree to a higher level. On the set of all full binarytrees with a given number of nodes there is about 1 jump for every 2 internal nodes, and the averagejump distance is about 2 levels. These averages are close to averages for trees that arise inpolynomial real root isolation.

关键词： algorithm analysis binary trees depth-first search catalan numbers

来源：评论

学校读者我要写书评

暂无评论

Helper and Equivalent Objectives: Efficient Approach for Constrained Optimization

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第1期52卷 240-251页

作者： Xu, Tao He, Jun Shang, Changjing Aberystwyth Univ Dept Comp Sci Aberystwyth SY23 3DB Dyfed Wales Nottingham Trent Univ Sch Sci & Technol Nottingham NG11 8NS England

Numerous multiobjective evolutionary algorithms (EAs) have been designed for constrained optimization over the past two decades. The idea behind these algorithms is to transform constrained optimization problems (COPs) into multiobjective optimization problems without any constraint, and then solve them. In this article, we propose a new multiobjective method for constrained optimization, which works by converting a COP into a problem with helper and equivalent objectives. An equivalent objective means that its optimal solution set is the same as that of the constrained problem but a helper objective does not. Then, this multiobjective optimization problem is decomposed into a group of subproblems using the weighted sum approach. Weights are dynamically adjusted so that each subproblem eventually tends to a problem with an equivalent objective. We theoretically analyze the computational time of the helper and equivalent objective method on a hard problem called "wide gap." In a wide gap problem, an algorithm needs exponential time to cross between two fitness levels (a wide gap). We prove that using helper and equivalent objectives can shorten the time of crossing the wide gap. We conduct a case study for validating our method. An algorithm with helper and equivalent objectives is implemented. The experimental results show that its overall performance is ranked first when compared with other eight state-of-the-art EAs on IEEE CEC2017 benchmarks in constrained optimization.

关键词： Optimization Linear programming Sociology Statistics Evolutionary computation Constraint handling Cybernetics algorithm analysis constrained optimization constraint handling evolutionary algorithms (EAs) multiobjective optimization objective decomposition

来源：评论

学校读者我要写书评

暂无评论

Order statistics and estimating cardinalities of massive data sets

引用

DISCRETE APPLIED MATHEMATICS 2009年第2期157卷 406-427页

作者： Giroire, Frederic INRIA Rocquencourt ALGO Project F-78153 Le Chesnay France

A new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data is introduced here. It is based on order statistics rather than on bit patterns in binary representations of numbers. Three families of estimators are analyzed. They attain a standard error of 1/root M using M units of storage. which places them in the same class as the best known algorithms so far. The algorithms have a very simple internal loop, which gives them an advantage in terms of processing speed. For instance, a memory of only 12 kB and only few seconds are sufficient to process a multiset with several million elements and to build an estimate with accuracy of order 2 percent. The algorithms are validated both by mathematical analysis and by experimentations on real internet traffic. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Cardinality estimates algorithm analysis Very large multisets Traffic analysis

来源：评论

学校读者我要写书评

暂无评论

Image segmentation algorithm based on partial differential equation

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2020年第4期38卷 3903-3909页

作者： Guo, Rui Shen, Xuanjing Kang, Hui Jilin Univ Coll Comp Sci & Technol Changchun 130012 Jilin Peoples R China

Image segmentation is very important for various fields. With the development of computer technology, computer technology has become more and more effective for image segmentation, and it is studied on the basis of partial differential equations. The curve representation method in plane differential geometry is expounded, with the SegNet-v2 segmentation model analyzed and tested in medical image segmentation. The test results show that the partial differential equation image segmentation algorithm can achieve more accurate segmentation, especially in medical image segmentation, which can achieve good results, and it is worth in practice to further promote.

关键词： Partial differential equation image segmentation algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Primality proving via one round in ECPP and one iteration in AKS

引用

JOURNAL OF CRYPTOLOGY 2007年第3期20卷 375-387页

作者： Cheng, Qi Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time Omicron (log(7.5) n) (heuristic time Omicron (log(6) n)). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve Primality Proving algorithm (ECPP) runs in random heuristic time 6 (log6 n) (some variant has heuristic time complexity Omicron(log(4) n)) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density Omicron(1/log(2) n)) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density (Omega (1/log log n)) of primes whose primality can be proved in time complexity 6(log4 n). For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily

关键词： computational number theory primality testing elliptic curve primality proving Agrawal-Kayal-Saxena primality-testing algorithm algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

The plurality problem with three colors and more

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期337卷 319-330页

作者： Aigner, M De Marco, G Montangero, M CNR Ist Informat & Telemat I-56124 Pisa Italy Free Univ Berlin Inst Math 2 D-14195 Berlin Germany Univ Salerno Dipartimento Informat & Applicaz I-84081 Baronissi Italy Univ Modena & Reggio Emilia Dipartimento Ingn Informaz I-41100 Modena Italy

The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L, (n) does Paul have to ask in the worst case? For c = 2, the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383-387). In this paper we show that 3 [n/2]-2 <= L-3 (n) <= [5n/3]-2. Moreover, for any c <= n, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal. (c) 2005 Elsevier B.V. All rights reserved.

关键词： combinatorial search algorithm analysis majority problem game

来源：评论

学校读者我要写书评

暂无评论

All-Pairs Shortest Path algorithms for planar graph for GPU-accelerated clusters

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 85卷 91-103页

作者： Djidjev, Hristo Chapuis, Guillaume Andonov, Rumen Thulasidasan, Sunil Lavenier, Dominique Los Alamos Natl Lab Los Alamos NM 87545 USA Los Alamos Natl Lab Informat Sci Grp CCS3 Los Alamos NM USA Los Alamos Natl Lab Computat Sci Div Los Alamos NM USA INRIA IRISA F-35042 Rennes France Univ Rennes 1 F-35042 Rennes France

We present a new approach for solving the All-Pairs Shortest-Path (APSP) problem for planar graphs that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPUs). We describe two new algorithms based on our approach. Both algorithms use Floyd-Warshall method, have near optimal complexity in terms of the total number of operations, while their matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation. (C) 2015 Elsevier Inc. All rights reserved.

关键词： All-pairs shortest path problem Planar graphs GPGPU Parallel computing Floyd-Warshall algorithm Distributed computing algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

A general modeling approach to online optimization with lookahead

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2016年 63卷 134-153页

作者： Dunke, Fabian Nickel, Stefan Karlsruhe Inst Technol Inst Operat Res Karlsruhe Germany

A vast number of real world problems are coined by an information release over time and the related need for repetitive decision making over time. Optimization problems arising in this context are called online since decisions have to be made although not all data is known. Due to technological advances, algorithms may also resort to a limited preview (lookahead) on future events. We first embed the paradigm of online optimization with lookahead into the theory of optimization and develop a concise understanding of lookahead. We further find that the effect of lookahead can be decomposed into an informational and a processual component. Based on analogies to discrete event systems, we then formulate a generic modeling framework for online optimization with lookahead and derive a classification scheme which facilitates a thorough categorization of different lookahead concepts. After an assessment of performance measurement approaches with relevance to practical needs, we conduct a series of computational experiments which illustrate how the general concept of lookahead applies to specific instantiations and how a knowledge pool on lookahead effects in applications can be built up using the general classification scheme. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Online optimization Lookahead Discrete event system algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

acc-Motif: Accelerated Network Motif Detection

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2014年第5期11卷 853-862页

作者： Meira, Luis A. A. Maximo, Vinicius R. Fazenda, Alvaro L. da Conceicao, Arlindo F. Univ Estadual Campinas UNICAMP Sch Technol Campinas SP Brazil Fed Univ Sao Paulo UNIFESP Inst Sci & Technol Sao Jose Dos Campos Brazil

Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al. [1], which provided motifs as a way to uncover the basic building blocks of most networks. Motifs have been mainly applied in Bioinformatics, regarding gene regulation networks. Motif detection is based on induced subgraph counting. This paper proposes an algorithm to count subgraphs of size k + 2 based on the set of induced subgraphs of size k. The general technique was applied to detect 3, 4 and 5-sized motifs in directed graphs. Such algorithms have time complexity O(a(G)m), O(m(2)) and O(nm(2)), respectively, where a(G) is the arboricity of G(V, E). The computational experiments in public data sets show that the proposed technique was one order of magnitude faster than Kavosh and FANMOD. When compared to NetMODE, acc-Motif had a slightly improved performance.

关键词： Network motifs algorithm analysis subgraph counting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：