A strong lower bound for approximate nearest neighbor searching

We prove a lower bound of d^1−o(1) on the query time for any deterministic algorithms that solve approximate nearest neighbor searching in Yao's cell probe model. Our result greatly improves the best previous lower bound for this problem, which is [A. Chakrabarti et al., in: Proc. 31st Ann. ACM Symp. Theory of Computing, 1999, pp. 305-311]. Our proof is also much simpler than the proof of A. Chakrabarti et al.     

低信噪比场景下Link-16系统的联合频偏估计算法

对于Link-16数据链终端平台在低信噪比(SNR)高动态场景下的多普勒频率偏移问题,该文设计一种新的数据结构,推导了该结构下的克拉默-拉奥下界(CRLB),并在此基础上提出一种联合频域变换与时域自相关运算的分步式频偏估计算法。其基本思想是,首先对接收信号做自相关处理,然后通过频域变换进行最大值索引,结合修正因子得到多普勒频移的粗估计值,再利用时域的改进L&R算法对接收信号进行细估计,根据两步估计算法得到最终的频偏估计值。算法应用蒙特卡罗实验仿真,仿真结果表明,与传统频偏估计算法相比,该算法的归一化均方误差更接近CRLB,在多普勒频偏为[–20 kHz, 20 kHz]时,估计精度可达10^–5。在低信噪比环境下,所提算法能达到较为理想的估计效果,适用于Link-16数据链通信。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

连续时间部分可观Markov决策过程的策略梯度估计

针对连续时间部分可观Markov决策过程(CTPOMDP)的优化问题,本文提出一种策略梯度估计方法. 运用一致化方法,将离散时间部分可观Markov决策过程(DTPOMDP)的梯度估计算法推广到连续时间模型, 研究了算法的收敛性和误差估计问题,并用一个数值例子来说明该算法的应用.     

Lower bound limit analysis using non‐linear programming

This paper describes a new formulation, based on linear finite elements and non‐linear programming, for computing rigorous lower bounds in 1, 2 and 3 dimensions. The resulting optimization problem is typically very large and highly sparse and is solved using a fast quasi‐Newton method whose iteration count is largely independent of the mesh refinement. For two‐dimensional applications, the new formulation is shown to be vastly superior to an equivalent formulation that is based on a linearized yield surface and linear programming. Although it has been developed primarily for geotechnical applications, the method can be used for a wide range of plasticity problems including those with inhomogeneous materials, complex loading, and complicated geometry. Copyright © 2002 John Wiley & Sons, Ltd.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

一种基于分散导频块的频偏估计新算法

针对短突发信号解调的需要,提出了一种基于分散导频块的频偏估计新算法。区别于以往基于连续导频的频偏估计算法,该算法除利用了导频本身已知信息外,还充分利用了导频的位置信息。在相同的帧效率下,相比于基于连续导频的频偏估计算法,该算法可以获得更好的估计性能。理论分析和仿真结果都表明,该算法在其无偏估计范围内估计性能达到了相应帧结构下的克拉美罗界。     

两种导管架海洋平台的系统可靠度分析

针对近海标准导管架平台和滩海单位柱平台这两种钢质导管架平台,将其简化为空间刚架结构,计算构成导管架平台各杆件的可靠度。以传统的微分等价递归算法为基础进行系统可靠性计算,并利用分枝-约界法差别两种平台的主要失效路径。基于上述研究结果,分析了两类导管架平台的失效特征和系统可靠度指标。