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

THE VLSI optimalITY OF THE AKS SORTING NETWORK

INFORMATION PROCESSING LETTERS 1985年第2期20卷 55-59页

作者： BILARDI, G PREPARATA, FP Coordinated Science Laboratory University of Illinois at Urbana-Champaign Urbana IL 61801 U.S.A.

It is shown that the AKS sorting network can indeed be laid out in area A equals O(n**2), while maintaining an O(log n) computation time, thereby establishing its optimality in the VLSI model of computation.

关键词： VLSI complexity area-time trade-off sorting networks optimal algorithms parallel computation

来源：评论

学校读者我要写书评

暂无评论

Digital phase-locked loops tracked by a relay sensor

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 1999年第5期47卷 667-669页

作者： Bonnet, C Partington, JR Sorine, M Inst Natl Rech Informat & Automat F-78153 Le Chesnay France Univ Leeds Sch Math Leeds LS2 9JT W Yorkshire England

An optimal algorithm is presented for tracking the phase of a slowly modulating signal by means of digital sampling of its sign. Error bounds and a numerical illustration are given.

关键词： demodulation digital control optimal algorithms phase-locked loop sampling

来源：评论

学校读者我要写书评

暂无评论

On lower complexity bounds for large-scale smooth convex optimization

引用

JOURNAL OF COMPLEXITY 2015年第1期31卷 1-14页

作者： Guzman, Cristobal Nemirovski, Arkadi Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

We derive lower bounds on the black-box oracle complexity of large-scale smooth convex minimization problems, with emphasis on minimizing smooth (with Holder continuous, with a given exponent and constant, gradient) convex functions over high-dimensional parallel to . parallel to(p)-balls, 1 <= p <= infinity. Our bounds turn out to be tight (up to logarithmic in the design dimension factors), and can be viewed as a substantial extension of the existing lower complexity bounds for large-scale convex minimization covering the nonsmooth case and the "Euclidean" smooth case (minimization of convex functions with Lipschitz continuous gradients over Euclidean balls). As a byproduct of our results, we demonstrate that the classical Conditional Gradient algorithm is near-optimal, in the sense of Information-Based Complexity Theory, when minimizing smooth convex functions over high-dimensional parallel to . parallel to(infinity)-balls and their matrix analogies - spectral norm balls in the spaces of square matrices. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Smooth convex optimization Lower complexity bounds optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Two machine scheduling subject to arbitrary machine availability constraint

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2018年 76卷 128-136页

作者： Huo, Yumei Zhao, Hairong CUNY Coll Staten Isl Dept Comp Sci Staten Isl NY 10314 USA Purdue Univ Northwest Dept Math Comp Sci & Stat Hammond IN 46323 USA

We study two machine scheduling subject to arbitrary machine availability constraint. Each machine can have multiple unavailable intervals, and both machines can be unavailable at the same time. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. We consider both the single criterion and the bi-criteria problems concerning two most common criteria: makespan and the total completion time. If makespan is, the single criterion to optimize, Liu and Sanlaville (1995) have shown that the optimal schedule can be found in polynomial time. If total completion time is the single criterion, the existing algorithm can only find the optimal schedules for some special cases;however, the complexity of the problem with arbitrary machine availability constraint remains open. For two bi-criteria problems, i.e., the problem of minimizing the total completion time subject to the constraint that the makespan is minimum, and the problem of minimizing makespan subject to the constraint that total completion time is minimum, their computational complexity are also open. In this paper, we show all these three open problems are in P by giving optimal algorithms that run in polynomial time. An interesting finding in this research is that these three problems are closely related to each other and thus the algorithms also rely on one another. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Arbitrary availability constraint Bi-criteria optimization optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT EREW PRAM algorithms FOR PARENTHESES-MATCHING

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第9期5卷 995-1008页

作者： PRASAD, SK DAS, SK CHEN, CCY UNIV N TEXAS DENTON TX 76203 USA TAMKANG UNIV DEPT COMP & INFORMAT ENGN TAIPEI TAIWAN

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log2 n) employing O(n/log n) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/log n) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, our last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms.

关键词： EREW PRAM optimal algorithms PARALLEL ALGORITHM PARENTHESES-MATCHING PARSING

来源：评论

学校读者我要写书评

暂无评论

ACCELERATION OF STOCHASTIC-APPROXIMATION BY AVERAGING

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1992年第4期30卷 838-855页

作者： POLYAK, BT JUDITSKY, AB INST RECH INFORMAT & SYST ALEATOIRES F-35042 RENNESFRANCE

A new recursive algorithm of stochastic approximation type with the averaging of trajectories is investigated. Convergence with probability one is proved for a variety of classical optimization and identification problems. It is also demonstrated for these problems that the proposed algorithm achieves the highest possible rate of convergence.

关键词： STOCHASTIC APPROXIMATION RECURSIVE ESTIMATION STOCHASTIC OPTIMIZATION optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

ON SOME UNION AND INTERSECTION PROBLEMS FOR POLYGONS WITH FIXED ORIENTATIONS

引用

COMPUTING 1986年第3期36卷 183-197页

作者： WIDMAYER, P WU, YF SCHLAG, MDF WONG, CK UNIV CALIF LOS ANGELES DEPT COMP SCILOS ANGELESCA 90024 NORTHWESTERN UNIV DEPT ELECT ENGN & COMP SCIEVANSTONIL 60201 IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598

Objects with fixed orientations play an important role in many application areas, for instance VLSI design. Problems involving only rectilinearly oriented (rectangular) objects, as a simplest case, have been studied with the VLSI design application in mind. These objects can be transistors, cells or macros. In reality, they are more suitably represented by polygons rather than just rectangles. In this note we describe how to perform a general decomposition of a set of polygons with fixed orientations in order to solve various computational geometry problems which are important in VLSI design. The decomposition is very simple and efficiently computable, and it allows the subsequent application of algorithms for the rectilinear case, leading to some very efficient and some optimal solutions. We illustrate the technique in detail at the problem of finding the connected components of a set of polygons, for which we derive an optimal solution. The wide applicability of the method is then demonstrated at the problem of finding all pairs of intersecting polygons, yielding an optimal solution.

关键词： 68C05 Polygons with fixed orientations computational geometry optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

SCALABILITY ASPECTS OF PARALLEL MULTIGRID

引用

FUTURE GENERATION COMPUTER SYSTEMS 1994年第4期10卷 429-439页

作者： LINDEN, J LONSDALE, G RITZDORF, H SCHULLER, A Gesellschaft für Mathematik und Datenverarbeitung mbH P.O. Box 1316 D-5205 St. Augustin 1 Germany

This paper summarizes theoretical and practical investigations into the effect of parallelization by grid-partitioning on the performance of multigrid methods for the solution of partial differential equations on general two-dimensional domains. Particular emphasis will be placed on the algorithmic scalability for MIMD distributed memory systems. Experimental results for two Navier-Stokes test problems, presented in the last section of the paper, show that the theoretically predicted dependency of the combined numerical and parallel efficiencies of multigrid methods on the number of processors employed is in fact very weak. This leads to the conclusion that multigrid is an appropriate candidate for solving partial differential equations on massively parallel machines.

关键词： PARALLEL MULTIGRID SCALABILITY optimal algorithms NAVIER-STOKES EQUATIONS

来源：评论

学校读者我要写书评

暂无评论

algorithms FOR PERMUTATION CHANNEL ROUTING

引用

INTEGRATION-THE VLSI JOURNAL 1987年第1期5卷 17-45页

作者： LEONG, HW LIU, CL UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

In this paper the channel routing problem is generalized to allow the interchange of some of the pins in the channel. The generalized problem is called the Permutation Channel Routing Problem (PCRP). This model arises naturally when there are logically equivalent (and therefore interchangeable) pins. Various other applications of the model are also presented. We show that the PCRP is NP-complete for two different cost measures. An optimal algorithm is presented for a special case called the Single Permutable Block Model. For the general PCRP, we study two methods of solution: iterative improvement and simulated annealing. Our results show that allowing some of the pins to be interchanged can lead to a substantial reduction in the number of tracks needed for routing. For example, by randomly generating a few small groups of interchangeable pins, a savings of 42% was obtained for Deutsch's Difficult problem. For all the test problems, our algorithms produce results that are very close to the best possible ones. We also show that our algorithms outperform a previous method by Kobayashi and Drozd.

关键词： Channel routing permutation channel routing interchangeable pins NP-completeness optimal algorithms iterative improvement simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Single-machine and two-machine flowshop scheduling with general learning functions

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第2期178卷 402-407页

作者： Koulamas, Christos Kyparisis, George J. Florida Int Univ Coll Business Adm Dept Decis Sci & Informat Syst Miami FL 33199 USA

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment. (c) 2006 Elsevier B.V. All rights reserved.

关键词： scheduling single machine flowshop shortest processing time learning optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：