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

Lower bounds and nonuniform time discretization for approximation of stochastic heat equations

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2007年第2期7卷 135-181页

作者： Mueller-Gronbach, Thomas Ritter, Klaus Univ Magdeburg Inst Math Stochast Fak Math D-39016 Magdeburg Germany Tech Univ Darmstadt Fachbereich Math D-64289 Darmstadt Germany

We study algorithms for approximation of the mild solution of stochastic heat equations on the spatial domain]0, 1 [(d). The error of an algorithm is defined in L-2-sense. We derive lower bounds for the error of every algorithm that uses a total of N evaluations of one-dimensional components of the driving Wiener process W. For equations with additive noise we derive matching upper bounds and we construct asymptotically optimal algorithms. The error bounds depend on N and d, and on the decay of eigenvalues of the covariance, of W in the case of nuclear noise. In the latter case the use of nonuniform time discretizations is crucial.

关键词： stochastic heat equation minimal error of algorithms lower bound optimal algorithm nonuniform time discretization

来源：评论

学校读者我要写书评

暂无评论

Batch delivery scheduling with batch delivery cost on a single machine

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第2期176卷 745-755页

作者： Ji, Min He, Yong Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Zhejiang Gongshang Univ Coll Comp Sci & Informat Engn Hangzhou 310035 Peoples R China Zhejiang Univ Dept Math State Key Lab CAD&CG Hangzhou 310027 Peoples R China

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B <= U for a variable U >= 2 or B >= U for any constant U >= 2. For the case of B <= U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U >= 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal. (c) 2005 Elsevier B.V. All rights reserved.

关键词： single machine scheduling batch delivery cost optimal algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

optimal algorithms for uncovering synteny problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第4期12卷 419-430页

作者： Ting, Chen Yong, H. E. Zhejiang Gongshang Univ Coll Stat & Comp Sci Hangzhou Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

The syntenic distance between two genomes is the minimum number of fusions, fissions, and translocations that can transform one genome to the other, ignoring the gene order within chromosomes. As the problem is NP-hard in general, some particular classes of synteny instances, such as linear synteny, exact synteny and nested synteny, are examined in the literature. In this paper, we propose a new special class of synteny instances, called uncovering synteny. We first present a polynomial time algorithm to solve the connected case of uncovering synteny optimally. By performing only intra-component moves, we then solve the unconnected case of uncovering synteny. We will further calculate the diameters of connected and unconnected uncovering synteny, respectively.

关键词： syntenic distance uncovering synteny optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

BMI approach to decentralized and cooperative control of large-scale system

引用

26th Chinese Control Conference

作者： Cao Li Nian Xiaohong Tang Wenyan Cent S Univ Sch Informat Sci & Engn Changsha 410075 Hunan Peoples R China

ISBN: (纸本)9787811240559

Based on the bilinear matrix inequality (BMI) technique, the problems of designing decentralized controllers and cooperative controllers of linear large-scale systems are considered. Necessary and sufficient conditions of the optimal decentralized and cooperative stabilization of the linear large-scale systems are obtained. The problems of designing decentralized and cooperative controllers are formulated into the non-convex optimization problems with BMI constraints. To solve these problems, the alternate optimized algorithms are proposed. Finally, example is given to illustrate the main results. It shows that a large-scale system can be stabilized via cooperative controllers or decentralized controllers and needs not presumer each subsystem be stable.

关键词： decentralized control cooperative control large-scale system optimal algorithm BMI

来源：评论

学校读者我要写书评

暂无评论

A new method of data classification in data reconciliation and its application

A new method of data classification in data reconciliation a...

引用

2nd IEEE Conference on Industrial Electronics and Applications (ICIEA 2007)

作者： Wu, Juan Shi, Hongbo E China Univ Sci & Technol Res Inst Automat Shanghai 200237 Peoples R China

ISBN: (纸本)9781424407361

The observability of a variable and the redundancy of a measurement are basic information in designing process performance monitoring systems. In these papers an optimal algorithm is described which allows the classification of the operation variables of chemical plants. The results of this procedure are used to reduce the size of the reconciliation problem.

关键词： reconciliation data reconciliation observabitity redundancy optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Coupling-aware dummy metal insertion for lithography 07

Coupling-aware dummy metal insertion for lithography

引用

12th Asia and South Pacific Design Automation Conference

作者： Deng, Liang Wong, Martin D. F. Chao, Kai-Yuan Xiang, Hua Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA

ISBN: (纸本)9781424406296

As integrated circuits manufacturing technology is advancing into 65nm and 45nm nodes, extensive resolution enhancement techniques (RETs) are needed to correctly manufacture a chip design. The widely used RET called off-axis illumination (OAI) introduces forbidden pitches which lead to very complex design rules. It has been observed that imposing uniformity on layout designs can substantially improve printability under OAI. For metal layers, uniformity can be achieved simply by inserting dummy metal wire segments at all free spaces. Simulation results indeed show significant improvement in printability with such a dummy metal insertion approach. To minimize mask cost, it is advantageous to use dummy metal segments that are of the same size as regular metal wires due to their simple geometry. But these dummy wires are printable and hence increase coupling capacitances and potentially affect yield. The alternative is to use a set of parallel sub-resolution thin wires (which will not be printed) to replace a printable dummy wire segment. These invisible dummy metal segments do not increase coupling capacitances but bring a higher lithography cost, which includes mask cost and RET/process expense. This paper presents a strategy for dummy metal insertion that can optimally trade off lithography cost and coupling capacitance. In particular, we present an optimal algorithm that can minimize lithography cost subject to any given coupling capacitance bound. Moreover, this dummy metal insertion will achieve a highly uniform density because of the locality of coupling capacitance, which automatically ameliorates chemical mechanical polish (CMP) problem.

关键词： optimal algorithm off-axis illumination lithography cost minimization resolution enhancement techniques printability improvement invisible dummy metal segments forbidden pitches chemical mechanical polish integrated circuits manufacturing technology coupling-aware dummy metal insertion

来源：评论

学校读者我要写书评

暂无评论

BASED ON SELF ORGANIZED EVOLUTIONARY algorithm FOR SOLVING CONSTRAINT PROBLEM

BASED ON SELF ORGANIZED EVOLUTIONARY ALGORITHM FOR SOLVING C...

引用

2007中国宁波国际计算机科学与技术学术大会

作者： Zhu Lili Zhao Kong Yuan Hua Yi Rongqin Wenzhou University School of Physics & Electronic Information Suzhou Top Institute of Information Technology Key Lab.of Symbol Computation & Knowledge Engineering of the Ministry of Education College of Computer Science & Technology Jilin University

ISBN: (纸本)9780972147903

The problem of parameterization design is equivalent to the problem of solving a set of nonlinear equations *** this paper,a new optimization algorithm—self organized evolutionary algorithm(SOEA) is proposed and applied into the parameterization *** SOEA the colony is composed of the *** organizational evolutionary operators which are split operator,mergence operator and coordination operator can lead the colony to *** three kinds of operators have different functions in the *** operator limits the scale of the organization and makes sure a part of organization comes into next generation directly,which maintains the variety of the *** operator makes use of the leader's information fully and acts as a local search *** operator increases the degree of adaptability between the two organizations by the *** experiment shows that SOEA has good capability in parameterization design.

关键词： optimal algorithm Geometric constraint solving Self organized evolutionary algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal Parallel algorithm for the Knapsack Problem Without Memory Conflicts

引用

Journal of Computer Science & Technology 2004年第6期19卷 760-768页

作者： Ken-LiLi Ren-FaLi Qing-HuaLi SchoolofComputerandCommunication HunanUniversityChangsha410082P.R.China SchoolofComputerScienceandTechnology HuazhongUniversityofScienceandTechnologyWuhan430074P.R.China

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches. Keywords knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict Supported by the National Natural Science Foundation of China under Grant No.60273075, the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06. Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization. Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing. Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid comp

关键词： knapsack problem NP-complete parallel algorithm optimal algorithm memory conflict

来源：评论

学校读者我要写书评

暂无评论

A New Method of Data Classification in Data Reconciliation and its Application

A New Method of Data Classification in Data Reconciliation a...

引用

2nd IEEE Conference on Industrial Electronics and Applications(ICIEA 2007)(第二届IEEE工业电子与应用国际会议)

作者： Juan WU Hongbo SHI East China University of Science and Technology China

关键词： Reconciliation Data reconciliation Observability Redundancy optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal scheduling for real-time parallel tasks

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2006年第6期E89D卷 1962-1966页

作者： Lee, WY Lee, H Hallym Univ Dept Comp Engn Chunchon 200702 South Korea Korea Univ Dept Comp Sci & Engn Seoul 136713 South Korea

We propose an optimal algorithm for the real-time scheduling of parallel tasks on multiprocessors, where the tasks have the properties of flexible preemption, linear speedup, bounded parallelism, and arbitrary deadline. The proposed algorithm is optimal in the sense that it always finds out a feasible schedule if one exists. Furthermore, the algorithm delivers the best schedule consuming the fewest processors among feasible schedules. In this letter, we prove the optimality of the proposed algorithm. Also, we show that the time complexity of the algorithm is O(M-2 - N-2.) in the worst case, where M and N are the number of tasks and the number of processors, respectively.

关键词： optimal algorithm real-time scheduling feasible schedule bounded parallelism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：