On the Curvature of the Central Path of Linear Programming Theory

We prove a linear bound on the average total curvature of the central path of linear programming theory in terms of the number of independent variables of the primal problem, and independent of the number of constraints.     

Optimal Path Planning Based on Visibility

Various problems associated with optimal path planning for mobile observers such as mobile robots equipped with cameras to obtain maximum visual coverage of a surface in the three-dimensional Euclidean space are considered. The existence of solutions to these problems is discussed first. Then, optimality conditions are derived by considering local path perturbations. Numerical algorithms for solving the corresponding approximate problems are proposed. Detailed solutions to the optimal path planning problems for a few examples are given.     

Thermal helium clusters at 3.2 Kelvin in classical and semiclassical simulations

The thermodynamic stability of⁴He_4–13 at 3.2 K is investigated with the classical Monte Carlo method, with the semiclassical path-integral Monte Carlo (PIMC) method, and with the semiclassical all-order many-body method. In the all-order many-body simulation the dipole-dipole approximation including short-range correction is used. The resulting stability plots are discussed and related to recent TOF experiments by Stephens and King. It is found that with classical Monte Carlo of course the characteristics of the measured mass spectrum cannot be resolved. With PIMC, switching on more and more quantum mechanics. by raising the number of virtual time steps results in more structure in the stability plot, but this did not lead to sufficient agreement with the TOF experiment. Only the all-order many-body method resolved the characteristic structures of the measured mass spectrum, including magic numbers. The result shows the influence of quantum statistics and quantum mechanics on the stability of small neutral helium clusters.     

A comparison of two algorithms for the assignment problem

State-of-the-art computational results have shown that the shortest augmenting path (SAP) methods are more efficient than other primal-dual and primal-simplex based methods for solving the linear assignment problem on uniprocessor computers. There is, however, some controversy concerning their merits when compared with Bertsekas' auction algorithm on multiprocessor computers. In this study we investigate the performance of these competing methods on the Alliant FX/8. For each method, theoretical motivation, sources of parallelism and computational results are presented.     

一类Lagrangian对偶问题的零对偶间隙性质及其最优路径的收敛性

针对一般的非线性规划问题,利用某些Lagrange型函数给出了一类Lagrangian对偶问题的一般模型,并证明它与原问题之间存在零对偶间隙．针对具体的一类增广La- grangian对偶问题以及几类由非线性卷积函数构成的Lagrangian对偶问题,详细讨论了零对偶间隙的存在性．进一步,讨论了在最优路径存在的前提下,最优路径的收敛性质．     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题，引进加权中心路径的概念，并利用单目标半定规划的中心路径法，提出了求解多目标半定规划问题的加权中心路径法，先得型对一个叔向量的有效解，然后在此基础上，提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．     

Farthest-point queries with geometric and combinatorial constraints

In this paper we discuss farthest-point problems in which a set or sequence S of n points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in O(log²n) time. Our data structure needs O(nlogn) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.     

红外耦合光学系统设计

红外目标模拟器由红外目标图像发生器和投影光学系统组成。该红外光学系统是一个要求与2个导引光学系统的光学技术参数相匹配的长焦距、大视场和具有像方远心光路的中红外光学系统。叙述用于红外目标模拟器的红外耦合光学系统的设计原理，提出它与导引光学系统一起可组成放大倍率M=4.5×的红外投影光学系统，并指出IR CRT产生的图像通过红外投影光学系统可成像在导引接收器上。针对给出的红外耦合光学系统的设计特点和技术要求，光学材料选取硅（Si） 锗（Ge） 硅（Si），采用简单的柯克三片式结构完成光学系统设计。设计评价结果表明，该系统的光学性能和成像质量均满足设计指标要求。     

汽车行驶的时间问题

就d>2R的情形解决如下组合几何极值问题:某平原地区有一个很大的湖泊.湖泊周围有两个村庄A,B.村庄A到村庄B的直线距离为已知.一辆汽车从A村庄出发以已知匀速速度驶向村B庄.问:若这辆汽车以最短路径行驶到达B村庄至多需要多少时间?