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

Performance evaluation of a parallel tabu search task scheduling algorithm

PARALLEL COMPUTING 2000年第1期26卷 73-90页

作者： Porto, SCS Kitajima, JPFW Ribeiro, CC Pontificia Univ Catolica Rio de Janeiro Dept Comp Sci Rio De Janeiro Brazil Univ Fed Fluminense Inst Computacao Niteroi RJ Brazil Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil

This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the achieved makespan reduction of different parallel applications, relatively to the results obtained by the best greedy algorithm in the literature, as a function of parameters such as problem size, system heterogeneity, and number of processors. Our results show that the parallel tabu search algorithm leads to much better solutions than the greedy algorithm in many cases where the latter is not capable of profiting from the inherent application parallelism and system heterogeneity, (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： parallel algorithms task scheduling greedy algorithm tabu search solution quality

来源：评论

学校读者我要写书评

暂无评论

An efficient reconfiguration algorithm for degradable VLSI/WSI arrays

引用

IEEE TRANSACTIONS ON COMPUTERS 2000年第6期49卷 553-559页

作者： Low, CP Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This paper considers the problem of reconfiguring two-dimensional degradable VLSI/WSI arrays under the constraint of row and column rerouting. The goal of the reconfiguration problem is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some specified minimum. This problem has been shown to be NP-complete under various switching and routing constraints. However, we show that a special case of the reconfiguration problem is optimally solvable in linear time. Using this result, a new fast and efficient reconfiguration algorithm is proposed. Empirical study shows that the new algorithm indeed produces good results in terms of the percentages of harvest and degradation of VLSI/WSI arrays.

关键词： degradable VLSI/WSI arrays NP-completeness greedy algorithm efficient heuristic

来源：评论

学校读者我要写书评

暂无评论

Structural aspects of ordered polymatroids

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期99卷 125-148页

作者： Krüger, U Univ Halle Wittenberg Inst Optimierung & Stochast FB Math & Informat D-06099 Halle Germany

This paper generalizes some aspects of polymatroid theory to partially ordered sets. The investigations are mainly based on Faigle and Kern (Math. Programming 72 (1996) 195-206). A slightly modified concept of submodularity is introduced. As a consequence many results do not require any assumptions concerning the underlying partially ordered groundset of the polymatroid. Our modified concept of submodularity especially guarantees that the greedy algorithm works for arbitrary posets. We discuss the facial structure of ordered polymatroids and consider two different basis concepts. These are Core(f), the set of all elements with maximal component sum, and Max(f), the set of all maximal feasible elements. Both concepts are equivalent for unordered polymatroids. The sets Core(f) and Max(f) are completely described by inducing inequalities. Furthermore, it is shown by an example that Max(f) is in general not a polyhedral set. Different ordered polymatroids may have the same core polytope. We will show that there is a unique smallest ordered polymatroid in the set of all ordered polymatroids with the same core polytope. (C) 2000 Elsevier Science B.V. All rights reserved. MSC. 90C27;52B12;90C10;05B35.

关键词： polyhedron face polymatroid base polytope greedy algorithm submodular poset

来源：评论

学校读者我要写书评

暂无评论

A switching algorithm for design of optimal increasing binary filters over large windows

引用

PATTERN RECOGNITION 2000年第6期33卷 1059-1081页

作者： Hirata, NST Dougherty, ER Barrera, J Texas A&M Univ Dept Elect Engn Comp Assisted Med Diagnost Imaging Lab College Stn TX 77843 USA Univ Sao Paulo Inst Math & Stat Dept Comp Sci BR-05508900 Sao Paulo Brazil

All known approaches for the design of increasing translation-invariant binary window filters involve combinatoric searches. This paper proposes a new switching algorithm having the advantage that the search is over a smaller set than other algorithms. Beginning with an estimate from image realizations of the optimal generic (nonincreasing) window function, the algorithm switches (exchanges) a set of observation vectors (templates) between the optimal function's kernel and the kernel's complement. There are many such "switching sets" that provide a kernel defining an increasing filter. The optimal increasing filter is the one corresponding to the switching set that produces the minimal increase in error over the optimal generic filter. The core of the search problem is the inversion set of the optimal filter. The inversion set is composed of all vectors in the kernel lying beneath a nonkernel vector in the lattice of observation vectors and all nonkernel vectors lying above a kernel vector. The new algorithm, which is based on an error-related greedy property, recursively eliminates the inversion set until the optimal increasing filter is obtained. For purposes of computational efficiency, the actual implementation may be based on a relaxation of the original construction, so that the result may be based on a relaxation of the original construction, so that the result may be suboptimal. For the various models tested, the relaxed algorithm has proven to be optimal or very close to optimal. Besides its good estimation precision, the new algorithm has three noteworthy properties: first, it is applicable to relatively large windows;second, it operates directly on the input data via estimates of the determining conditional probabilities;and third, the degree of relaxation serves as an input parameter to the algorithm, so that computation time can be bounded for large windows and the algorithm can run to full optimality for small windows. (C) 2000 Pattern Recognition Soci

关键词： increasing filter optimal filter nonlinear filler Boolean lattice switching algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Iterative dynamic programming: A new class of query optimization algorithms

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2000年第1期25卷 43-82页

作者： Kossmann, D Stocker, K Univ Passau Lehrstuhl Dialogorientierte Syst D-94030 Passau Germany

The query optimizer is one of the most important components of a database system. Most commercial query optimizers today are based on a dynamic-programming algorithm, as proposed in Selinger et al. [1979]. While this algorithm produces good optimization results (i.e., good plans), its high complexity can be prohibitive if complex queries need to be processed, new query execution techniques need to be integrated, or in certain programming environments (e.g., distributed database systems). In this paper, we present and thoroughly evaluate a new class of query optimization algorithms that are based on a principle that we call iterative dynamic programming, or IDP for short. IDP has several important advantages: First, IDP-algorithms produce the best plans of all known algorithms in situations in which dynamic programming is not viable because of its high complexity. Second, some IDP variants are adaptive and produce as good plans as dynamic programming if dynamic programming is viable and as-good-as possible plans if dynamic programming turns out to be not viable. Three, all IDP-algorithms can very easily be integrated into an existing optimizer which is based on dynamic programming.

关键词： algorithms performance query optimization dynamic programming iterative dynamic programming randomized optimization greedy algorithm plan evaluation function

来源：评论

学校读者我要写书评

暂无评论

Greedily finding a dense subgraph

引用

JOURNAL OF algorithmS 2000年第2期34卷 203-221页

作者： Asahiro, Y Iwama, K Tamaki, H Tokuyama, T Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka 812 Japan Kyoto Univ Sch Informat Kyoto 60601 Japan Meiji Univ Dept Comp Sci Kawasaki Kanagawa 21471 Japan IBM Corp Tokyo Res Lab Yamato 242 Japan

Given an n-vertex graph with nonnegative edge weights and a positive integer k less than or equal to n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)(2) - O(n(-1/3)) less than or equal to R less than or equal to (1/2 + n/2k)(2) + O(1/n) for k in the range n/3 less than or equal to k less than or equal to n and 2(n/k - 1)- O(1/k) less than or equal to R less than or equal to 2(n/k - 1) + O(n/k(2)) for k < n/3. For k = n/2, for example, these bounds are 9/4 +/- O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best land much more complicated) approximation algorithm based on semidefinite programming. (C) 2000 Academic Press.

关键词： ROENTGEN Equal greedy algorithm Approximation algorithms total laden weight Upper bound Less than or equal to

来源：评论

学校读者我要写书评

暂无评论

On the core of ordered submodular cost games

引用

MATHEMATICAL PROGRAMMING 2000年第3期87卷 483-499页

作者： Faigle, U Kern, W Univ Cologne Zentrum Angew Informat Math Inst D-50931 Cologne Germany Univ Twente Dept Appl Math NL-7500 AE Enschede Netherlands

A general ordertheoretic linear programming model fur the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the ease with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed.

关键词： core N-person game greedy algorithm Monge property order polymatroid poset submodular

来源：评论

学校读者我要写书评

暂无评论

NJML: A hybrid algorithm for the neighbor-joining and maximum-likelihood methods

引用

MOLECULAR BIOLOGY AND EVOLUTION 2000年第9期17卷 1401-1409页

作者： Ota, S Li, WH Univ Chicago Dept Ecol & Evolut Chicago IL 60637 USA

In the reconstruction of a large phylogenetic tree, the most difficult part is usually the problem of how to explore the topology space to find the optimal topology. We have developed a "divide-and-conquer" heuristic algorithm in which an initial neighbor-joining (NJ) tree is divided into subtrees at internal branches having bootstrap values higher than a threshold. The topology search is then conducted by using the maximum-likelihood method to reevaluate all blanches with a bootstrap value lower than the threshold while keeping the other branches intact. Extensive simulation showed that our simple method, the neighbor-joining maximum-likelihood (NJML) method, is highly efficient in improving NJ trees. Furthermore, the performance of the NJML method is nearly equal to or better than existing time-consuming heuristic maximum-likelihood methods. Our method is suitable for reconstructing relatively large molecular phylogenetic trees (number of taxa greater than or equal to 16).

关键词： phylogenetic reconstruction topology search subtrees greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating binary images from discrete X-rays

引用

SIAM JOURNAL ON OPTIMIZATION 2000年第2期11卷 522-546页

作者： Gritzmann, P De Vries, S Wiegelmann, M Tech Univ Munich Zentrum Math D-80290 Munich Germany

We study the problem of approximating binary images that are accessible only through few evaluations of their discrete X-ray transform, i.e., through their projections counted with multiplicity along some lines. This inverse discrete problem belongs to a class of generalized set partitioning problems and allows natural packing and covering relaxations. For these ( NP-hard) optimization problems we present various approximation algorithms and provide estimates for their worst-case performance. Further, we report on computational results for various variants of these algorithms. In particular, the corresponding integer programs are solved with only small absolute error for instances up to 250, 000 binary variables.

关键词： discrete tomography set packing set covering set partitioning greedy algorithm matching approximation algorithm worst-case performance polynomial time

来源：评论

学校读者我要写书评

暂无评论

A neural-greedy combination algorithm for board-level routing in FPGA-based logic emulation systems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1998年第5期E81A卷 866-872页

作者： Funabiki, N Kitamichi, J Osaka Univ Sch Engn Sci Dept Informat & Comp Sci Toyonaka Osaka 5608531 Japan

An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m greater than or equal to 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N x M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. [12]. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.

关键词： FPGA board-level routing NP-complete digital neural network greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：