关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

Counterexamples in measuring the distance between binary trees

Examples are given to show that the closest partition distance measure need not agree with the nearest neighbor interchange distance for unordered labeled binary trees. Proposed algorithms for computing the closest partition distance are shown to be of exponential complexity and hence may not be useful in approximating the nearest neighbor interchange distance.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

A Point Balance Algorithm for the Spherical Code Problem

The Spherical Code (SC) problem has many important applications in such fields as physics, molecular biology, signal transmission, chemistry, engineering and mathematics. This paper presents a bilevel optimization formulation of the SC problem. Based on this formulation, the concept of balanced spherical code is introduced and a new approach, the Point Balance Algorithm (PBA), is presented to search for a 1-balanced spherical code. Since an optimal solution of the SC problem (an extremal spherical code) must be a 1-balanced spherical code, PBA can be applied easily to search for an extremal spherical code. In addition, given a certain criterion, PBA can generate efficiently an approximate optimal spherical code on a sphere in the n-dimensional space ⁿ. Some implementation issues of PBA are discussed and putative global optimal solutions of the Fekete problem in 3, 4 and 5-dimensional space are also reported. Finally, an open question about the geometry of Fekete points on the unit sphere in the 3-dimensional space is posed.     

Solving Nonconvex Planar Location Problems by Finite Dominating Sets

It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location.In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems.Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed - to polynomial approximation algorithms with accuracy for solving the general model considered in this paper.     

基于蚁群算法的二维最大熵分割算法

由于二维最大熵分割法不仅考虑了像素的灰度信息,而且还充分利用了像素的空间邻域信息,因此能够取得较好的分割效果.但是,该方法的计算量巨大,不利于红外图像的快速处理.蚁群算法于20世纪90年代初提出,是受到蚁群集体行为的启发而提出的一种基于种群的模拟进化算法,属于随机搜索算法.该算法已经成功应用于旅行商等离散问题.将蚁群算法应用于二维最大熵法,提出了基于蚁群算法的二维最大熵分割算法.与传统的穷尽搜索法相比,求解速度提高了60倍左右.仿真实验表明,该方法快速、简单、有效.     

一种相位提取算法误差特性的分析

设计了一种新的相位提取算法，根据推导的评价函数，研究了其误差特性，与传统相位提取算法做了比较分析，其频域特性有了显著提高．分析结果证明该算法对失谐误差不敏感，高阶偶数谐波误差对结果值也不敏感，具有比较优势．仿真实验结果验证了理论预期．     

惯导辅助相对导航系统在漂移坐标系中的相对定位算法

对惯导辅助相对导航系统（JTIDS／INS）组网，根据相对坐标漂移概念和理论，本文详细介绍了辅助相对位置基准的相对位置滤波、相对坐标漂移滤波和在漂移坐标系中进行相对定位的特点和算法，并进行了组网仿真，仿真结果满足系统技术性能要求。     

一种基于分层回溯的数据库查询优化算法

结合DP算法和回溯法的基本思想，提出了一种新的基于分层回溯的查询优化算法。其在优化简单查询时，可以提供“最优”的方案；对于一些复杂的应用环境，它可以在杖举算法的高复杂性和算法产生方案的质量之间取得一个权衡点，以产生“次优”的优化结果来换取算法的执行效率，大大节省了运行环境的资源。     

Active mode leakage reduction using fine-grained forward body biasing strategy

Leakage power minimization has become an important issue with technology scaling. Variable threshold voltage schemes have become popular for standby power reduction. In this work we look at another emerging aspect of this potent problem which is leakage power reduction in active mode of operation. In gate level circuits, a large number of gates are not switching in active mode at any given point in time but nevertheless are consuming leakage power. We propose a fine-grained forward body biasing (FBB) scheme for active mode leakage power reduction in gate level circuits without any delay penalty. Our results show that our optimal polynomial time FBB allocation algorithm results in 70.2% reduction in leakage currents. We also present an exact standard-cell placement driven FBB allocation algorithm that effectively reduces the area penalty using the post-placement area slack and results in 56.5%, 62.8% and 66.1% reduction in leakage currents for 0%, 4% and 8% area slack, respectively. Furthermore, we present a heuristic to solve the standard-cell placement driven FBB allocation problem that is computationally efficient and results in leakage within 2% of that from the exact formulation.