P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

Fuzzy relation equations theory as a basis of fuzzy modelling: An overview

We give a wide overview on the applications of fuzzy relation equations theory to decision-making processes, to the construction of preference relations and to Knowledge Engineering, mainly fuzzy control and fuzzy pattern recognition. General theoretical results and methodological aspects are pointed out.     

Interior point algorithms for linear programming with inequality constraints

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.     

关于隐式LU分解算法分解算法求矩阵主子阵逆的注记（英）

ＡＲｅｍａｒｋｏｎｔｈｅＩｎｖｅｒｓｅｏｆＰｒｉｎｃｉｐａｌＭａｔｒｉｃｅｓｂｙＩｍｐｌｉｃｉｔＬＵＦａｃｔｏｒｉｚａｔｉｏｎＨｕａｎｇＫａｉｂｉｎＷｕＨｅｂｉｎ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＮａｎｊｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉ...     

Disintegration of Gaussian measures and average-case optimal algorithms

It is shown that a Gaussian measure in a given infinite-dimensional Banach space always admits an essentially unique Gaussian disintegration with respect to a given continuous linear operator. This covers a similar statement made earlier in [Lee and Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2(1) (1986) 12–43.] for the case of finite-rank operators.     

On the computation of the optimal cost function for discrete time Markov models with partial observations

We consider several applications of two state, finite action, infinite horizon, discrete-time Markov decision processes with partial observations, for two special cases of observation quality, and show that in each of these cases the optimal cost function is piecewise linear. This in turn allows us to obtain either explicit formulas or simplified algorithms to compute the optimal cost function and the associated optimal control policy. Several examples are presented.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, in part by the Advanced Technology Program of the State of Texas, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Additive Schwarz algorithm for the nonlinear complementarity problem with M-function

In this paper, an additive Schwarz algorithm is considered for solving the finite-dimensional nonlinear complementarity problem with M-function. The monotone convergence of the algorithm is obtained with special choices of initial values. Moreover, the weighted max-norm bound is obtained for the iterative errors.     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

Space-Time Point-Process Models for Earthquake Occurrences

Several space-time statistical models are constructed based on both classical empirical studies of clustering and some more speculative hypotheses. Then we discuss the discrimination between models incorporating contrasting assumptions concerning the form of the space-time clusters. We also examine further practical extensions of the model to situations where the background seismicity is spatially non-homogeneous, and the clusters are non-isotropic. The goodness-of-fit of the models, as measured by AIC values, is discussed for two high quality data sets, in different tectonic regions. AIC also allows the details of the clustering structure in space to be clarified. A simulation algorithm for the models is provided, and used to confirm the numerical accuracy of the likelihood calculations. The simulated data sets show the similar spatial distributions to the real ones, but differ from them in some features of space-time clustering. These differences may provide useful indicators of directions for further study.     

Implementing an efficient minimum capacity cut algorithm

In this paper, we present an efficient implementation of theO(mn + n ² logn) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration. To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved.Corresponding author.