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

DYNAMIC-PROGRAMMING IS optimal FOR NON-SERIAL OPTIMIZATION PROBLEMS

SIAM JOURNAL ON COMPUTING 1982年第1期11卷 47-59页

作者： ROSENTHAL, A

We consider discrete optimization problems in which the only exploitable feature of the objective function is a limited form of decomposability. “Nonoverlapping comparison algorithms” are defined as a model of procedures which decompose the problem and apply Bellman’s principle of optimality. Nonserial dynamic programming (DP), a simple elimination procedure, is shown to be optimal among all nonoverlapping comparison algorithms, including nondeterministic algorithms. These results can give an exponential lower bound on the shortest admissible proof that a solution is optimal. Furthermore, if part of the search space is ruled out, a subset of the comparisons made by DP optimally searches the remainder. We suggest that the running time of DP is a useful measure of the “interaction complexity” of a problem, and that because of its simplicity DP is of practical as well as theoretical interest.

关键词： nonserial dynamic programming optimal algorithms lower bound exponential time comparision algorithms perfect elimination graph decomposition complexity dynamic programming

来源：评论

学校读者我要写书评

暂无评论

AN optimal ALGORITHM FOR PROCESSING DISTRIBUTED STAR QUERIES

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1985年第10期11卷 1097-1107页

作者： CHEN, ALP LI, VOK UNIV SO CALIF DEPT ELECT ENGNLOS ANGELESCA 90089

For distributed database systems, the optimal processing of queries has been extremely difficult. In the present paper, a polynomial time algorithm for optimal distributed query processing is developed for the special class of star queries. The algorithm is based on the use of semijoin tactics to process queries. Initially, semijoin programs involved in distributed query processing are modeled in an execution graph, and optimality properties for star query semijoin programs are derived. Then, through serial semijoin strategies, where each semijoin having exactly one association with the query is included, the optimal semijoin program is determined. Polynomial time determination of the optimal semijoin program is accomplished through implementation of certain assumptions about file size and semijoin selectivities that allow reduction in the number of optimal semijoin programs that needs to be considered.

关键词： Star Queries Distributed Database Systems optimal algorithms Query Optimization Relational Data Model Semijoin Programs Semijoin Selectivity

来源：评论

学校读者我要写书评

暂无评论

optimal Functional Unit Assignment and Voltage Selection for Pipelined MPSoC with Guaranteed Probability on Time Performance 2017

Optimal Functional Unit Assignment and Voltage Selection for...

引用

18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)

作者： Jiang, Weiwen Sha, Edwin H. -M. Zhuge, Qingfeng Dong, Hailing Chen, Xianzhang Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China

ISBN: (纸本)9781450350303

Pipelined heterogeneous multiprocessor system-on-chip (MPSoC) can provide high throughput for streaming applications. In the design of such systems, time performance and system cost are the most concerning issues. By analyzing runtime behaviors of benchmarks in real-world platforms, we find that execution times of tasks are not fixed but spread with probabilities. In terms of this feature, we model execution times of tasks as random variables. In this paper, we study how to design high-performance and low-cost MPSoC systems to execute a set of such tasks with data dependencies in a pipelined fashion. Our objective is to obtain the optimal functional unit assignment and voltage selection for the pipelined MPSoC systems, such that the system cost is minimized while timing constraints can be met with a given guaranteed probability. For each required probability, our proposed algorithm can efficiently obtain the optimal solution. Experiments show that other existing algorithms cannot find feasible solutions in most cases, but ours can. Even for those solutions that other algorithms can obtain, ours can reach 30% reductions in total cost compared with others.

关键词： Functional unit assignment application-specific system energy efficiency probabilistic execution time optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Sorting N items using a p-sorter in optimal time

Sorting N items using a p-sorter in optimal time

引用

8th IEEE Symposium on Parallel and Distributed Processing

作者： Olariu, S Zheng, SQ Old Dominion Univ Norfolk United States

ISBN: (纸本)0818676833

A sorting device capable of sorting p items in constant time is cabled a p-sorter. It is known that the task of sorting N items using a p-sorter requires at least Omega (N log N/p log p) applications of the p-sorter. This bound is tight: there exist algorithms that use O (N log N/p log p) calls to the p-sorter to sort N items. However, there is no known implementable algorithm that can sort N items in O (N log N/p log p) time using a p-sorter. The main contribution of this paper is to propose a simple VLSI architecture and to show that in our architecture N items can be sorted in O (N log N/p log p) calls to the p-sorter, while enforcing conflict-free memory accesses. An important feature of our design is that the total additional VLSI area for hardware, other than the memory for data and the p-sorter, is kept to a minimum.

关键词： special-purpose architectures VLSI sorting p-sorter optimal algorithms parallel algorithms reconfigurable mesh

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Approach to optimal Estimation Part I: Problem Formulation and Methodology

A Probabilistic Approach to Optimal Estimation Part I: Probl...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Inst I-10129 Turin Italy Northeastern Univ Boston MA 02115 USA

ISBN: (纸本)9781467320665

The classical approach to system identification is based on statistical assumptions about the measurement error and provides estimates that have stochastic nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds and provides guaranteed estimates. The focal point of this paper is to provide a rapproachement between these two paradigms and propose a novel probabilistic framework for system identification. The main idea in this line of research is to "discard" sets of measure at most epsilon, where epsilon is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic "risk." The main results of the paper establish rigorous theoretical properties of a trade-off curve, called optimal violation function, which shows how the radius of information decreases as a function of the accuracy. In the companion paper [8], we develop algorithms (randomized and deterministic) which exploit these theoretical results for efficiently computing the optimal violation function.

关键词： System identification optimal algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

An optimal Concepts for Aggregation of Data in Wireless Sensor Network 2

An Optimal Concepts for Aggregation of Data in Wireless Sens...

引用

IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON)

作者： Galkin, Pavlo Klyuchnyk, Igor Kharkiv Natl Univ Radioelect Dept Design & Operat Elect Devices Kharkiv Ukraine

ISBN: (纸本)9781728138824

In this paper propose an several concepts for optimal algorithm of aggregation of data in wireless sensor network. Given analysis of problems for information aggregation in wireless sensor network. Proposed optimise of structure the node and given basic concepts for reducing energy consumption. Also proposed network partitioning into piconet with next clustering. In final proposed are two modifications for ant algorithms to optimize data collection in wireless sensor network.

关键词： wireless sensor network optimal algorithms aggregation of data data collection CC2530

来源：评论

学校读者我要写书评

暂无评论

optimal Three-Layer Channel Routing

引用

IEEE Transactions on Computers 1984年第5期C-33卷 427-437页

作者： Preparata, Franco P. Lipski, Witold Coordinated Science Laboratory University of Illinois at Urbana-Champaign Urbana IL 61801 United States Institute of Computer Science Polish Academy of Sciences Warsaw P.O. Box 22 Poland

In this paper we show that any channel routing problem of density d involving only two-terminal nets can always be solved in the knock-knee mode in a channel of width equal to the density d with three conducting layers. An algorithm is described which produces in time 0(n log n) (in its simplest implementation) a layout of n nets with the following properties: 1) it has minimal width d;2) it can be realized with three layers;3) it has at most 3n vias;4) any two wires share at most four grid points. Without sacrificing any of the above properties (but possibly obtaining slightly longer wires), the layout algorithm can be modified to run in time 0(n). © 1984 IEEE

关键词： Channel routing multilayer wiring optimal algorithms VLSI design VLSI layouts

来源：评论

学校读者我要写书评

暂无评论

optimal Functional-Unit Assignment and Buffer Placement for Probabilistic Pipelines 16

Optimal Functional-Unit Assignment and Buffer Placement for ...

引用

International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS)

作者： Jiang, Weiwen Sha, Edwin H. -M. Zhuge, Qingfeng Chen, Xianzhang Chongqing Univ Coll Comp Sci Chongqing Peoples R China

ISBN: (纸本)9781450344838

Applications, such as streaming applications, modeled by task graphs can be efficiently executed in a pipelined fashion. In synthesizing application-specific heterogeneous pipelined systems, where to place buffers (called buffer placement) and what type of functional units to execute each task (called functional assignment) are two critical problems. In reality, the execution time of each task may not be fixed, which makes the above two problems much more challenging. In this paper, we model the execution time of each task on different types of functional units as a random variable. Our objective is to obtain the optimal functional assignment and buffer placement, such that the resultant pipeline can satisfy the timing requirement with the minimum cost under the guaranteed confidence probability. This paper presents efficient algorithms to achieve the objective. Experiments show that other techniques cannot find any feasible solutions in many cases while ours can. Even for the cases where they can find feasible solutions, our algorithms achieve the minimum cost which gives a significant reduction on the total cost, compared with existing techniques.

关键词： High-level synthesis application-specific system optimal algorithms probabilistic scenario

来源：评论

学校读者我要写书评

暂无评论

An Algorithm for the optimal Solution of Linear Inequalities and Its Application to Pattern Recognition

引用

IEEE Transactions on Computers 1973年第12期C-22卷 1065-1075页

作者： Warmack, Ralph E. Gonzalez, Rafael C. Department of Electrical Engineering University of Tennessee Knoxville. Tenn. 37916 United States Department of Electrical Engineering University of Tennessee Knoxville Tenn. 37916 United States

An algorithm for the optimal solution of consistent and inconsistent linear inequalities is presented, where the optimality criterion is the maximization of the number of satisfied constraints. The algorithm is developed as a nonenumerative search procedure based on two new theorems established in this paper. It is shown that the number of iterative steps before termination is strictly less than that required by an exhaustive search. Experimental results with various types of data establish the computational tractability of the procedure under nontrivial conditions. Copyright © 1973 by The Institute of Electrical and Electronics Engineers, Inc.

关键词： algorithms linear inequalities mathematical programming optimal algorithms pattern recognition threshold logic

来源：评论

学校读者我要写书评

暂无评论

An excellent derivative-free multiple-zero finding numerical technique of optimal eighth order convergence

引用

Annali dell'Universita di Ferrara 2022年第1期68卷 161-186页

作者： Sharma, Janak Raj Kumar, Sunil Department of Mathematics Sant Longowal Institute of Engineering and Technology Sangrur Longowal 148106 India Department of Mathematics Amrita School of Engineering Amrita Vishwa Vidyapeetham Channai 601103 India

A number of higher order Newton-like methods (i.e. the methods requiring both function and derivative evaluations) are available in literature for multiple zeros of a nonlinear function. However, higher order Traub-Steffensen-like methods (i.e. the methods requiring only function evaluations) for computing multiple zeros are rare in literature. Traub-Steffensen-like iterations are important in the circumstances when derivatives are complicated to evaluate or expensive to compute. Motivated by this fact, here we present an efficient and rapid-converging Traub-Steffensen-like algorithm to locate multiple zeros. The method achieves eighth order convergence by using only four function evaluations per iteration, therefore, this convergence rate is optimal. Performance is demonstrated by applying the method on different problems including some real life models. The computed results are compared with that of existing optimal eighth-order Newton-like techniques to reveal the computational efficiency of the new approach. © 2022, The Author(s) under exclusive license to Università degli Studi di Ferrara.

关键词： Iteration function Multiple roots Nonlinear equations optimal algorithms Traub-Steffensen method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：