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

An optimal algorithm for the minimum disc cover problem

ALGORITHMICA 2008年第1期50卷 58-71页

作者： Sun, Min-Te Yi, Chih-Wei Yang, Chuan-Kai Lai, Ten-Hwang Auburn Univ Dept Comp Sci & Software Engn Auburn AL 36849 USA Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30010 Taiwan Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei 106 Taiwan Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general alpha-hull problem. In spite of being a special case, the disc cover problem is not easier than the general alpha-hull problem. In addition to applying the existing alpha-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the alpha-hull approach would fail.

关键词： minimum disc cover alpha-hull optimal algorithms applications in ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

A one-step worst-case optimal algorithm for bi-objective univariate optimization

引用

OPTIMIZATION LETTERS 2014年第7期8卷 1945-1960页

作者： Zilinskas, Antanas Vilnius State Univ Inst Math & Informat Akademijos St 4 LT-08663 Vilnius Lithuania

A bi-objective optimization problem with univariate non-convex objectives is considered. The objective functions are assumed Lipschitz continuous. An algorithm is developed implementing the concept of one-step worst case optimality. The possibility of extension of the proposed algorithm to the multivariate case is discussed. Some illustrative numerical examples are included where the proposed algorithm is compared with an average case optimal algorithm.

关键词： Multi-objective optimization optimal algorithms Global optimization Lipschitz optimization

来源：评论

学校读者我要写书评

暂无评论

optimal learning of bandlimited functions from localized sampling

引用

JOURNAL OF COMPLEXITY 2009年第2期25卷 85-114页

作者： Micchelli, Charles A. Xu, Yuesheng Zhang, Haizhang Syracuse Univ Dept Math Syracuse NY 13244 USA SUNY Albany Dept Math & Stat Albany NY 12222 USA Chinese Acad Sci Acad Math & Syst Sci Inst Math Beijing 100190 Peoples R China

An optimal algorithm for approximating bandlimited functions from localized sampling is established. Several equivalent formulations for the approximation error of the optimal algorithm are presented and its upper and lower bound estimates for the univariate case are provided. The estimates show that the approximation error decays exponentially (but not faster) as the number of localized samplings increases. As a consequence of these results, we obtain an upper bound estimate for the eigenvalues of an integral operator that arises in the bandwidth problem. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Whittaker-Shannon series Bandlimited signals optimal algorithms Error estimates Translation invariant kernels The bandwidth problem

来源：评论

学校读者我要写书评

暂无评论

Modified descend curvature based fixed form fuzzy optimal control of nonlinear dynamical systems

引用

COMPUTERS & CHEMICAL ENGINEERING 2006年第5期30卷 878-888页

作者： Oysal, Y Becerikli, Y Konar, AF Anadolu Univ Dept Comp Engn Eskisehir Turkey Kocaeli Univ Dept Comp Engn Kocaeli Turkey Dogus Univ Dept Comp Engn Istanbul Turkey

In this study, a fuzzy rule-based optimal controller is designed for nonlinear dynamical systems. The direct second order method (or direct-descend-curvature algorithm) with a modification called "modified descend controller (MDC)" is used for calculating the parameters of the fuzzy feedback controller. The optimal control problem defined here has dynamic constraints of nonlinear system states and static constraint of a known form of fuzzy controller. The form used here is a standard fuzzy system that uses singleton fuzzifier, product inference engine, center average defuzzifier, and with the Gaussian membership functions of the system states to be controlled. The design is developed by minimizing a quadratic performance index selected for the desired operating conditions. Successful simulation results of controlling the temperature of a continuous stirred tank reactor (CSTR) and a bioreactor are given. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： fixed form optimal control fuzzy control optimal algorithms intelligent control

来源：评论

学校读者我要写书评

暂无评论

Periodicity in optimal hierarchical checkpointing schemes for adjoint computations

引用

OPTIMIZATION METHODS & SOFTWARE 2017年第3期32卷 594-624页

作者： Aupy, Guillaume Herrmann, Julien Vanderbilt Univ Dept Elect Engn & Comp Sci 221 Kirkland Hall Nashville TN 37235 USA Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA

We reexamine the work of Aupy et al. on optimal algorithms for hierarchical adjoint computations, where two levels of memories are available. The previous optimal algorithm had a quadratic execution time. Here, with structural arguments, namely periodicity, on the optimal solution, we provide an optimal algorithm in constant time and space, with appropriate pre-processing. We also provide an asymptotically optimal algorithm for the online problem, when the adjoint chain size is not known before-hand. Again, these algorithms rely on the proof that the optimal solution for hierarchical adjoint computations is weakly periodic. We conjecture a closed-form formula for the period. Finally, we assess the convergence speed of the approximation ratio for the online problem through simulations.

关键词： optimal algorithms online asymptotic optimality checkpointing adjoint computation program reversal automatic differentiation 65Y20 68W40 49N45 90C30

来源：评论

学校读者我要写书评

暂无评论

optimal SYSTOLIC DESIGN FOR THE TRANSITIVE CLOSURE AND THE SHORTEST-PATH PROBLEMS

引用

IEEE TRANSACTIONS ON COMPUTERS 1987年第5期36卷 603-614页

作者： KUNG, SY LO, SC LEWIS, PS Signal and Image Processing Institute Department of Electrical Engineering University of Southern California

Due to VLSI technological progress, algorithm- oriented array architectures, such as systolic arrays, appear to be very effective, feasible, and economic. This paper discusses how to design systolic arrays for the transitive closure and the shortest path problems. We shall focus on the Warshall algorithm for the transitive closure problem and the Floyd algorithm for the shortest path problem. These two algorithms share exactly the same structural formulation; therefore, they lead to the same systolic array design. In this paper, we first present a general method for mapping algorithms to systolic arrays. Using this methodology, two new systolic designs for the Warshall-Floyd algorithm will be derived. The first one is a spiral array, which is easy to derive and can be further simplified to a hexagonal array. The other is an orthogonal systolic array which is optimal in terms of pipelining rate, block pipelining rate, and the number of input/output connections.

关键词： Algorithm mappings VLSI algorithms VLSI architectures optimal algorithms shortest path problem systolic arrays transitive closure problems

来源：评论

学校读者我要写书评

暂无评论

Synthesizing distributed pipelining systems with timing constraints via optimal functional unit assignment and communication selection

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2018年 26卷 332-343页

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

The design of efficient optimization techniques is important to synthesize application-specific distributed systems with timing constraints. In many applications, represented by task graphs, the consecutive executions of a task graph can be overlapped in a pipelined fashion with a proper buffer placement. The performance of such a system is closely related to the behavior of pipelining. Given a timing (throughput) constraint, however, using the fastest functional units or communication protocols may incur unacceptable high cost. In the design of such distributed pipelining systems with timing constraint, several problems need to be solved: how to properly place buffers, assign functional unit types for each task, and select communication protocols for each pair of tasks. This paper presents efficient optimization algorithms by integrally considering the above problems, such that the resultant systems can satisfy the timing constraints with the minimum total cost. In this paper, we first study the properties of distributed pipelining systems by using a rigorous model, called self-timed model, and then we present theorems to accurately compute the system throughput. Based on these understandings, we devise efficient algorithms to obtain the optimal solutions. Experiments show that the typical greedy approaches cannot find a feasible solution for the tight timing requirements while our algorithms can. For the few cases that greedy approaches may find solutions, our algorithms can achieve significant reductions in total cost. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed pipelining system Timing performance Cost minimization optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A new optimal algorithm for weighted approximation and integration over R

引用

NUMERICAL algorithms 2000年第4期23卷 393-406页

作者： Han, L Wasilkowski, GW Univ Kentucky Dept Comp Sci Lexington KY 40506 USA

The complexities of weighted approximation and weighted integration problems for univariate functions defined over R have recently been found in [7]. Complexity (almost) optimal algorithms have also been provided therein. In this paper, we propose another class of (almost) optimal algorithms that, for a number of instances, are easier to implement. More importantly, these new algorithms have a cost smaller than the original algorithms from [7]. Since both classes of algorithms are (almost) optimal, their costs differ by a multiplicative constant that depends on the specific weight functions and the error demand. In one of our tests we observed this constant to be as large as four, which means a cost reduction by a factor of four.

关键词： weighted approximation weighted integration optimal algorithms complexity

来源：评论

学校读者我要写书评

暂无评论

AN optimal WORST CASE ALGORITHM FOR REPORTING INTERSECTIONS OF RECTANGLES

引用

IEEE TRANSACTIONS ON COMPUTERS 1980年第7期29卷 571-577页

作者： BENTLEY, JL WOOD, D CARNEGIE MELLON UNIV DEPT MATHPITTSBURGHPA 15213 MCMASTER UNIV COMP SCI UNITHAMILTON L8S 4L8ONTARIOCANADA

In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large-scale integrated (VLSI) circuits and architectural databases. We describe an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found. This algorithm is optimal to within a constant factor. As an intermediate step of this algorithm, we solve a problem related to the range searching problem that arises in database applications. Although the algorithms that we describe are primarily theoretical devices (being very difficult to code), they suggest other algorithms that are quite practical.

关键词： Computational geometry VLSI design rule checking geometric intersection problems optimal algorithms range searching

来源：评论

学校读者我要写书评

暂无评论

optimal WIRING OF MOVABLE TERMINALS

引用

IEEE TRANSACTIONS ON COMPUTERS 1983年第9期32卷 845-858页

作者： GOPAL, IS COPPERSMITH, D WONG, CK IBM CORP THOMAS J WATSON RES CTRDEPT MATH SCIYORKTOWN HTSNY 10598

In this paper we consider the problem of local wiring in a VLSI chip. The problem is one of interconnecting two sets of terminals, one set on each side of a wiring channel, in accordance with a given interconnection pattern, and to accomplish this while minimizing some objective function. We make the further assumption that the terminals are not rigidly positioned and can be "moved" provided that this does not change the structural intent of the circuit. Several objective functions are considered-channel width, channel length, channel area, channel perimeter, number of via holes, as well as some constrained objective functions. For some of these objective functions, we are able to find polynomial time optimal algorithms while, for others, we prove NP-completeness and suggest efficient heuristics.

关键词： Analysis of algorithms NP-complete problems VLSI chip design dynamic programming movable terminals optimal algorithms vias wiring wiring channels

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：