A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

The Limit Distribution of the Largest Interpoint Distance from a Symmetric Kotz Sample

Generalizing recent work of P. C. Matthews and A. L. Rukhin (Ann. Appl. Probab.3(1993), 454–466), we obtain the limit law of the largest interpoint Euclidean distance for a spherically symmetric multivariate sample of the Kotz distribution. While going through the proof, some errors in the reasoning given by Matthews and Rukhin are pointed out and corrected.     

车灯配光性能在线检测系统研究

本文介绍一种能够对车灯光度、色度性能同时进行在线测试的计量仪器。它操作方便，精度较高，符合国标对车灯配光性能检测的要求。     

两个空间变量的拟线性抛物方程初值问题解的正则性

本文研究了两个空间变量的拟线性退缩抛物方程Ｃａｕｃｈｙ问题广义解的正则性问题。推广了文献［１］的结果。     

Approximating dominant singular triplets of large sparse matrices via modified moments

A procedure for determining a few of the largest singular values and corresponding singular vectors of large sparse matrices is presented. Equivalent eigensystems are solved using a technique originally proposed by Golub and Kent based on the computation of modified moments. The asynchronicity in the computations of moments and eigenvalues makes this method attractive for parallel implementations on a network of workstations. Although no obvious relationship between modified moments and the corresponding eigenvectors is known to exist, a scheme to approximate both eigenvalues and eigenvectors (and subsequently singular values and singular vectors) has been produced. This scheme exploits both modified moments in conjunction with the Chebyshev semi-iterative method and deflation techniques to produce approximate eigenpairs of the equivalent sparse eigensystems. The performance of an ANSI-C implementation of this scheme on a network of UNIX workstations and a 256-processor Cray T3D is presented.This research was supported in part by the National Science Foundation under grant numbers NSF-ASC-92-03004 and NSF-ASC-94-11394.     

涉及微分多项式的亚纯函数的唯一性

设ｆ（ｚ）是非常数的整函数，ｎ是正整数，Ｆ（ｚ）＝ｆ￣（ｎ）（ｚ）＋ａ＿１（ｚ）ｆ￣（ｎ－１）（ｚ）＋…＋ａ＿ｎ（ｚ）ｆ（ｘ），其中ａ＿１（ｚ），ａ＿２（ｚ），…，ａ＿ｎ（ｚ）均是ｆ（ｚ）的小函数，本文证明了：若ｆ（ｚ）和Ｆ（ｚ）几乎ＣＭ分担两个不同的有穷复数ａ和ｂ，则ｆ（ｚ）≡Ｆ（ｚ）．     

A NEW FIXED POINT THEOREM FOR CONE MAPS AND ITS APPLICATIONS

1IntroductionLetEbearealBanachspace.AnonemptyconvexclosedsetPCEiscalledaconeinEifitsatisfiesthefollowingtwoconditionsf(i)xEP,A20impliesAxEP,(n)xEP,--xEPimpliesx=0.AconePiscalledsolidifitcontainsinteriorpoints,i.e.,P/gi.TheconePinEdefinesapartialorderingx5…     

一类2阶边值问题的分歧点

本文考虑以下２阶边值问题：其中．在关于Ａ，Ｂ；Ｐ，Ｑ，ｆ的一定条件下，证明了以上问题存在分歧点．所用的主要工具是Ｋｒａｓｎｏｓｅｌｓｋｉｉ的局部分歧定理与ＫｒｅｉｎＲｕｔｍａｎ定理．     

关于一类连续最优控制问题的一种可实现的离散方法

本文对具有状态终端约束、控制受限的非线性连续最优控制问题给出一种新的可实现的离散方法，此方法通过求解非线最小二乘问题避免这类问题离散后出现的不可行现象，文中给出这种做法的理论证明和实现方案。