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村庄至多需要多少时间?     

外力J(t)作用下一维谐振子的传播子计算

用路径积方法计算了外力J(t) =f0 t( f0 为常量 )作用下谐振子的传播子 ,并由此求得能量本征函数与本征值     

低温二维电子气体的比热容

运用闭路格林函数方法，得到了二维电子气体热力学势的表达式，同时还得到了新的交换项，这个交换项可以化为已知的由虚时方法得到的表达式，但在低温下它没有奇异性，这表明，虽然闭路格林函数方法和虚时方法在总体上是等价的，但在一些技术细节上前者优于后者，此外，从导出的热力学势出发计算了二维电子气体在低温下的比热容。     

Corrections of proofs for Hansen and Mélot's two theorems

The Randi? index R(G) of a (chemical) graph G is also called connectivity index. Hansen and Mélot [Variable neighborhood search for extremal graphs 6: analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci. 43 (2003) 1-14] in their paper, characterized the chemical trees of given order and number of pendent vertices which have the minimum and maximum Randi? index, respectively. In this note, we point out the mistakes in the proofs of their results Theorems 8 and 10, while we still believe that the two theorems are true, and then we give their corrected proofs.