Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

线性规划的符号跟踪算法

分析了只含一个约束条件的线性规划最优基变量的特征，将其运用到搜寻含m个约束条件的线性规划的最优基变量，从而提出了线性规划的符号跟踪算法，为线性规划求解提供了新途径。     

多周期公用工程系统运行的模型,优化方法与应用

针对多周期公用工程系统的运行优化问题，考虑了设备的启停费用的情况下。建立了混合整数非线性规划模型并证明了最优解的存在性。针对该运行优化问题本将其分解成若干子问题，然后利用改进的Hooke-Jeeves优化算法求解每个子问题。应用于具体实例，其数值结果与其它方法得到的相比。运行时间短，且更适合多周期公用工程问题的求解。     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

红外图像掠海小目标的检测算法研究

针对红外图像掠海小目标信噪比低，且易受到水天线和背景杂波干扰的特点，提出了一种红外掠海小目标的提取与检测算法。该方法的特点是：首先采用中值滤波来减小噪声，并提出了差方和算法，用以抑制背景噪声并对目标增强；再采用了图像行扫描法有效地滤除水天线；最后通过弱化背景边缘和阈值分割等综合算法得到候选小目标。仿真结果表明，该算法达到了较好的效果。     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

Affine scaling algorithm fails for semidefinite programming

In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere.     

第二讲合成孔径声纳成像及其研究进展

文章在介绍了图像声纳的特点、合成孔径声纳（synthetic aperture sonar,SAS）产生背景和发展过程的基础上,对合成孔径声纳的原理、技术难点、成像算法等问题进行了讨论.着重分析了合成孔径声纳成像过程中高分辨率的获取方法、水声信道对成像的影响、多子阵技术及其成像算法、稳定的声纳运动平台和运动监测问题、运动补偿与自聚焦方法等.文章还给出了国内外合成孔径声纳研究的最新进展情况,进而展望了合成孔径声纳的应用前景.     

关系模式关键字的一个求解算法

本文给出了关系数据库模式中求解关键字的一个算法。算法很简洁并且对于[1]定义的一大类问题,执行时间是多项式级的。     

Decomposition of organic salts of some d and f metals

The thermal decomposition in non-isothermal conditions of formates, acetates, propionates and butyrates of Mn, Co, Zn, Cd, Eu, Sm and Ni was studied. The observed compensation effect allows us to calculate the isokinetic temperature. A selective activation mechanism was suggested. This leads to a good agreement between kinetic and spectroscopic data. This revised version was published online in July 2006 with corrections to the Cover Date.