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

Mathematical complexity of running filters on semi-groups and related problems

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第7期56卷 3191-3197页

作者： Coltuc, Dinu Valahia Univ Targoviste Dept Elect Engn Bucharest Romania INP GIPSA Lab Grenoble France

This paper proves that the mathematical complexity of running filters on semi-groups is C(p) = 3 - (6/(p + 1)) operations per sample, where p is the filter window. On other algebraic structures, the mathematical complexity of the filtering can be lower. Two such cases are investigated: the running filtering on max/min lattice and on additions group. They correspond to max/min and moving average filters. It is shown that the algorithms developed for semi-groups are of interest in such cases, too. Thus, the fastest deterministic algorithm for max/min filtering known so far is based on an algorithm for running filtering on semi-groups. First, an optimized version is proposed in this paper. Then, further improvement for data-dependent max/min algorithms is proposed. Finally, the case of moving average and exponential smoothing is investigated. Their implementation by using the algorithms for semi-groups is of lower complexity than the classical recursive implementation for the particular case of small size windows (p = 3 and p = 4).

关键词： fast algorithms fast max/min filters fast moving average mathematical complexity optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel merging with restriction

引用

JOURNAL OF SUPERCOMPUTING 2008年第1期43卷 99-104页

作者： Bahig, Hazem M. Ain Shams Univ Dept Math Div Comp Sci Fac Sci Cairo Egypt

In this paper, we study the merging of two sorted arrays A = (a(1), a(2), ..., a(n1)) and B = (b(1), b(2), ..., b(n2)) on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1, n], where n = Max(n(1), n(2)). (2) The elements are taken from either uniform distribution or non-uniform distribution such that #{a is an element of A and b is an element of B s.t.a, b is an element of [(i - 1)n/p + 1, i n/p]} = O(n/p), for 1 <= i <= p (number of processors). We give a new optimal deterministic algorithm runs in O(n/p) time using p processors on EREW PRAM. For p = n/log((g)) n;the running time of the algorithm is O(log((g)) n) which is faster than the previous results, where log((g)) n = loglog((g-1)) n for g > 1 and log((1)) n = log n. We also extend the domain of input data to [1, n(k)], where k is a constant.

关键词： parallel algorithms optimal algorithms integer merging EREW PRAM

来源：评论

学校读者我要写书评

暂无评论

Quantifying spatial misallocation in centrally provided public goods

引用

ECONOMICS LETTERS 2008年第2期98卷 201-206页

作者： Athreya, Siva Somanathan, Rohini Delhi Sch Econ Delhi India Indian Stat Inst Bangalore 560059 Karnataka India

We use an optimization algorithm to solve a two-period planner's problem of spatially allocating public goods. We apply the algorithm to data on the location of post offices in South India between 1981-1991 and show that more appropriate choices could have reduced travel costs by at least 20%. (c) 2007 Elsevier B.V. All rights reserved.

关键词： public goods optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal online algorithms for multidimensional packing problems

引用

SIAM JOURNAL ON COMPUTING 2005年第2期35卷 431-448页

作者： Epstein, L Van Stee, R Univ Haifa Dept Math IL-31905 Haifa Israel Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany

We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. Its asymptotic performance ratio is (Pi(infinity))(d), where Pi(infinity) approximate to 1.691 is the asymptotic performance ratio of the one-dimensional algorithm Harmonic. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Furthermore, we extend the techniques used in these algorithms to give optimal algorithms for online bounded space variable-sized packing and resource augmented packing.

关键词： multidimensional bin packing online algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple Monte Carlo and the metropolis algorithm

引用

JOURNAL OF COMPLEXITY 2007年第4-6期23卷 673-696页

作者： Mathe, Peter Novak, Erich Univ Jena Math Inst D-07743 Jena Germany Weierstrass Inst Appl Anal & Stochast D-10117 Berlin Germany

We study the integration of functions with respect to an unknown density. Information is available as oracle calls to the integrand and to the non-normalized density function. We are interested in analyzing the integration error of optimal algorithms (or the complexity of the problem) with emphasis on the variability of the weight function. For a corresponding large class of problem instances we show that the complexity grows linearly in the variability, and the simple Monte Carlo method provides an almost optimal algorithm. Under additional geometric restrictions (mainly log-concavity) for the density functions, we establish that a suitable adaptive local Metropolis algorithm is almost optimal and outperforms any non-adaptive algorithm. (c) 2007 Elsevier Inc. All rights reserved.

关键词： Monte Carlo methods metropolis algorithm log-concave density rapidly mixing Markov chains optimal algorithms adaptivity complexity

来源：评论

学校读者我要写书评

暂无评论

A note on two fixed point problems

引用

JOURNAL OF COMPLEXITY 2007年第4-6期23卷 952-961页

作者： Boonyasiriwat, Ch. Sikorski, K. Xiong, Ch. Univ Utah Sch Comp Salt Lake City UT 84112 USA Univ Utah Dept Chem Salt Lake City UT 84112 USA

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n(2) ln(2/epsilon) on the number of function evaluations for finding epsilon-residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry. (c) 2007 Elsevier Inc. All rights reserved.

关键词： fixed point problems optimal algorithms nonlinear equations Ellipsoid algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Dynamic energy aware task scheduling using run-queue peek

Dynamic energy aware task scheduling using run-queue peek

引用

International Conference on Parallel and Distributed Computing and Networks

作者： Pawaskar, Sachin Ali, Hesham H. Univ Nebraska Dept Comp Sci Omaha NE 68182 USA

ISBN: (纸本)9780889866379

Scheduling dependent tasks is one of the most challenging problems in parallel and distributed systems. It is known to be computationally intractable in its general form as well as several restricted cases. An interesting application of scheduling is in the area of energy awareness for mobile battery operated devices where minimizing the energy utilized is the most important scheduling policy consideration. A number of heuristics have been developed for this consideration. In this paper, we study the scheduling problem for a particular battery model. In the proposed work, we show how to enhance a well know approach of accounting for the slack generated at runtime due to the difference between WCET (Worst Case Execution Time) and AET (Actual Execution Time). Our solution exploits the fact that even though some tasks become available based on the actual periodicity of a task they are not executed because the run queue is determined by the schedule generated in the offline phase I of the algorithm using the conservative EDF (Earliest Deadline First) algorithm. We peek at the task run-queue to find such tasks to eliminate wastage of the slack generated. Based on the outcome of the conducted experiments, the proposed algorithm outperformed or matched the performance of the 2-Phase dynamic task scheduling algorithm all the time.

关键词： scheduling energy awareness heuristics parallel processing optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for bound and equality constrained quadratic programming problems with bounded spectrum

引用

COMPUTING 2006年第4期78卷 311-328页

作者： Dostal, Z. Tech Univ Ostrava Ostrava 70833 Czech Republic

An implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for solving the large convex bound and equality constrained quadratic programming problems is considered. It is proved that if the algorithm is applied to the class of problems with uniformly bounded spectrum of the Hessian matrix, then the algorithm finds an approximate solution at O(1) matrix-vector multiplications. The optimality results are presented that do not depend on conditioning of the matrix which defines the equality constraints. Theory covers also the problems with dependent constraints. Theoretical results are illustrated by numerical experiments.

关键词： quadratic programming bound and equality constraints augmented Lagrangians optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：