一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

证券组合的Markov链模型

本文将证券价格时间序列分解成趋势变动序列和 Markov链 ,建立了证券组合的 Markov链模型 ,应用 Markov链理论对此模型进行了分析 ,给出了充分大的一个时间内的收益率 ,风险和切点组合的计算公式     

Asymptotic Uniqueness of Best Rational Approximants of Given Degree to Markov Functions in L 2 of the Circle

We improve over a sufficient condition given in [8] for uniqueness of a nondegenerate critical point in best rational approximation of prescribed degree over the conjugate-symmetric Hardy space of the complement of the disk. The improved condition connects to error estimates in AAK approximation, and is necessary and sufficient when the function to be approximated is of Markov type. For Markov functions whose defining measure satisfies the Szego condition, we combine what precedes with sharp asymptotics in multipoint Padé approximation from [43], [40] in order to prove uniqueness of a critical point when the degree of the approximant goes large. This lends perspective to the uniqueness issue for more general classes of functions defined through Cauchy integrals.     

Nonstationary Continuous-Time Markov Control Processes with Discounted Costs on Infinite Horizon

This paper concerns nonstationary continuous-time Markov control processes on Polish spaces, with the infinite-horizon discounted cost criterion. Necessary and sufficient conditions are given for a control policy to be optimal and asymptotically optimal. In addition, under suitable hypotheses, it is shown that the successive approximation procedure converges in the sense that the sequence of finite-horizon optimal cost functions and the corresponding optimal control policies both converge.     

约束最小支撑树 ( C-MST)问题: 复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 N P-完 全的 . 然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 ,最后分析了解的平面 性质 .     

Singularly Perturbed Markov Chains: Convergence and Aggregation

Asymptotic properties of singularly perturbed Markov chains having measurable and/or continuous generators are developed in this work. The Markov chain under consideration has a finite-state space and is allowed to be nonstationary. Its generator consists of a rapidly varying part and a slowly changing part. The primary concerns are on the properties of the probability vectors and an aggregated process that depend on the characteristics of the fast varying part of the generators. The fast changing part of the generators can either consist of l recurrent classes, or include also transient states in addition to the recurrent classes. The case of inclusion of transient states is examined in detail. Convergence of the probability vectors under the weak topology of L² is obtained first. Then under slightly stronger conditions, it is shown that the convergence also takes place pointwise. Moreover, convergence under the norm topology of L² is derived. Furthermore, a process with aggregated states is obtained which converges to a Markov chain in distribution.     

Filtering of Finite-State Time-Nonhomogeneous Markov Processes, a Direct Approach

A filtering equation is derived for P(x _t =x|y _s ,s∈[0,t]) for a continuous-time finite-state two-component time-nonhomogeneous cadlag Markov process z _t =(x _t ,y _t ) . The derivation is based on some new ideas in the filtering theory and does not require any knowledge of stochastic integration. Accepted 10 August 1999. Online publication 13 November 2000.     

Algorithmic Aspects of Tree Amalgamation

The amalgamation of leaf-labeled trees into a single (super)tree that “displays” each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

On a synchronization queue with two finite buffers

In this paper, we consider a synchronization queue (or synchronization node) consisting of two buffers with finite capacities. One stream of tokens arriving at the system forms a Poisson process and the other forms a PH-renewal process. The tokens are held in the buffers until one is available from each flow, and then a group-token is instantaneously released as a synchronized departure. We show that the output stream of a synchronization queue is a Markov renewal process, and that the time between consecutive departures has a phase type distribution. Thus, we obtain the throughput of this synchronization queue and the loss probabilities of each type of tokens. Moreover, we consider an extended synchronization model with two Poisson streams where a departing group-token consists of several tokens in each buffer. This revised version was published online in June 2006 with corrections to the Cover Date.