Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

Second order algorithms for the posynomial geometric programming dual,part I: Analysis

In this paper we analyse algorithms for the geometric dual of posynomial programming problems, that make explicit use of second order information. Out of two possible approaches to the problem, it is shown that one is almost always superior. Interestingly enough, it is the second, inferior approach that has dominated the geometric programming literature.This work was partially supported by the National Research Council of Canada, Grant A3552 and National Science Foundation Grant ENG78-21615.Earlier versions of this paper were presented at the Optimization Days Conference in Montreal (May 1976) and the TIMS meeting in Athens (July 1977).     

A statistical model for global optimization by means of select and clone

A statistical model tor giobai optimization is constructed generalizing some properties ofthe Wiener process to the multidimensional case. A new approach, which is similar to the Branch and Bound approach, is proposed to the construction of algorithms based on statistical models. A two dimensional version of the algorithm is implemented, and test results are presented     

用遗传算法研究Con(n=3-60)团簇的结构特性

我们采用半经验的Gupta多体势结合遗传算法,系统地研究了Con(n=3-60)团簇的几何结构特性.我们发现在钴团簇的生长中存在一个类fcc构型与类Ih构型之间的竞争,从n=39开始,钴团簇呈现出明显的Ih生长模式.Con(n=3-60)团簇的幻数为13,19,23,38,55,结合钴团簇的平均最近邻原子间距和平均配位数,分析了钴团簇幻数序列存在的原因.我们发现团簇内部原子具有增强团簇对称性和加强团簇稳定性的显著作用.     

Computer Simulation of a 3-D Sensing System with Structured Illumination

A computer simulation system of three-dimensional sensing with structured illumination is presented. It includes the generation of deformed fringe patterns from 3-D shapes and the reconstruction of 3-D shapes, conversely. Some experimental results of the deformed fringe pattern and the reconstructed object shapes are presented. We have also discussed the effect of some major system parameters on the measurement results and considered how to correct these parameters according to the measurement result of the standard plane. Using this simulation system, the major system parameters: environmental conditions, measurement accuracy and algorithm evaluation of the 3-D shape measurement system based on PMP, FTP, SPM, etc., can be researched. © 1997 Elsevier Science Ltd. All rights reserved.     

Projection conditions on the vorticity in viscous incompressible flows

The problem of establishing appropriate conditions for the vorticity transport equation is considered. It is shown that, in viscous incompressible flows, the boundary conditions on the velocity imply conditions of an integral type on the vorticity. These conditions determine a projection of the vorticity field on the linear manifold of the harmonic vector fields. Some computational consequences of the above result in two-dimensional calculations by means of the nonprimitive variables, stream function and vorticity, are examined. As an example of the application of the discrete analogue of the projection conditions, numerical solutions of the driven cavity problem are reported.