On the number of full levels in tries

We study the asymptotic distribution of the fill‐up level in a binary trie built over n independent strings generated by a biased memoryless source. The fill‐up level is the number of full levels in a tree. A level is full if it contains the maximum allowable number of nodes (e.g., in a binary tree level k can have up to 2^k nodes). The fill‐up level finds many interesting applications, e.g., in the internet IP lookup problem and in the analysis of level compressed tries (LC tries). In this paper, we present a complete asymptotic characterization of the fill‐up distribution. In particular, we prove that this distribution concentrates on one or two points around the most probably value k = ?log_1/qn ? log log log n + 1 + log log(p/q)?, where p > q = 1 ? p is the probability of generating the more likely symbol (while q = 1 ? p is the probability of the less likely symbol). We derive our results by analytic methods such as generating functions, Mellin transform, the saddle point method, and analytic depoissonization. We also present some numerical verification of our results. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Isotone relations revisited

We propose a new approach towards proving that the fixed point property for ordered sets is preserved by products. This approach uses a characterization of fixed points in products via isotone relations. First explorations of classes of isotone relations are presented. These first explorations give us hope that this approach could lead to advances on the Product Problem.     

An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

Boundary value problems for first order impulsive delay differential equations with a parameter

In this paper, by means of the method of upper and lower solutions and monotone iterative technique, the existence of maximal and minimal solutions of the boundary value problems for first order impulsive delay differential equations is established.     

On the existence of positive solutions for a class of singular boundary value problems

In this paper, by the use of a fixed point theorem, many new necessary and sufficient conditions for the existence of positive solutions in C[0,1]∩C¹[0,1]∩C²(0,1) or C[0,1]∩C²(0,1) are presented for singular superlinear and sublinear second-order boundary value problems. Singularities at t=0, t=1 will be discussed.     

Existence of two solutions of m-point boundary value problem for second order dynamic equations on time scales

In this paper, by means of a new twin fixed-point theorem in a cone, the existence of at least two positive solutions of m-point boundary value problem for second order dynamic equations on time scales is considered.     

Interior point cutting plane method for optimal power flow

In this paper, an interior point cutting plane method (IPCPM)is applied to solve optimal power flow (OPF) problems. Comparedwith the simplex cutting plane method (SCPM), the IPCPM is simpler,and efficient because of its polynomial-time characteristic.Issues in implementing IPCPM for OPF problems are addressed,including (1) how to generate cutting planes without using thesimplex tableau, (2) how to identify the basis variables inIPCPM, and (3) how to generate mixed integer cutting planes.The calculation speed of the proposed algorithm is further enhancedby utilizing the sparsity features of the OPF formulation. Numericalsimulations on IEEE 14-300-bus test systems have shown thatthe proposed method is effective.     

斐索型光学合成孔径系统近轴成像条件研究

从几何光学理论出发，详细推导了斐索型光学合成孔径成像系统的近轴非相干成像条件，即子望远系统的角放大率等于系统的线性缩放因子。对于焦平面上的像点而言，合成孔径成像系统可等效为一个带有特殊形状孔径光阑的望远系统，这要求该孔径光栏的开口形状和位置分布与合成孔径成像系统各子系统孔径大小和位置分布相一致。我们由此得到了斐索型合成孔径成像系统的主要约束条件。     

具有无限时滞的二阶微分方程解的存在性

§ 1.　IntroductionRecently ,thedifferentialequationswithdeviatingargumentswereusuallydiscussed(see[1 ],[4],[5 ]) .In [1 ],AGARWALRPandO’REGANDconsideredequationy″(t) =f(t,y(t) ,y(σ(t) ) ) ,　a.e .t∈ [0 ,1 ]y(t) =ψ(t) ,　　　　　　　　t∈ [-r ,0 ]y( 1 ) =a ,( )andtheydiscussedtheexistenceofatleastonesolutionforequation ( ) .Inthispaper ,weconsideramoregeneralequation-x″(t) =f(t ,xt) ,　t∈ [0 ,1 ]x(t) =ψ(t) ,　　　　t∈ ( -∞ ,0 ]x( 0 ) =x( 1 ) =0 ,( 1 .1 )andsomeexistencetheor…     

一些随机重合点定理

本文引入了一种满足更一般的收缩不等式的多重函数类,并证明了属于该类的可测多重函数对的一些随机重合点定理。