0N THE COMPLEXITY OF AN OPTIMAL ROUTING TREE PROBLEM

A routing tree for a set of tasks is a decision tree which assigns the tasks to their destinationsaccording to the features of the tasks. A weighted routing tree is one with costs attached to each linkof the tree. Links of the same feature have the same cost. It is proved that the problem of finding ?routing tree of the minimum cost for a given set of tasks of two features is NP-complete.     

First passage models for denumerable semi-Markov decision processes with nonnegative discounted costs

This paper considers a first passage model for discounted semi-Markov decision processes with denumerable states and nonnegative costs.The criterion to be optimized is the expected discounted cost incurred during a first passage time to a given target set.We first construct a semi-Markov decision process under a given semi-Markov decision kernel and a policy.Then,we prove that the value function satisfies the optimality equation and there exists an optimal(or e-optimal) stationary policy under suitable conditions by using a minimum nonnegative solution approach.Further we give some properties of optimal policies.In addition,a value iteration algorithm for computing the value function and optimal policies is developed and an example is given.Finally,it is showed that our model is an extension of the first passage models for both discrete-time and continuous-time Markov decision processes.     

On the restricted arc-connectivity of s-geodetic digraphs

For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.     

s-REGULAR DIHEDRAL COVERINGS OF THE COMPLETE GRAPH OF ORDER 4

§1. Introduction For a ?nite, simple, and undirected graph X, every edge of X gives rise to a pair ofopposite arcs, and we denote by V (X), E(X), A(X) and Aut(X) the vertex set, the edgeset, the arc set and the automorphism group of X, respectively. …     

A PROPERTY OF HERMITE-PADE INTERPOLATION ON THE ROOTS OF UNITY

We extend a theorem of Ivanev and Saff to show that for the Hermite-Pade interpolant at the roots of unity to a function meromorphic in the unit disc, its leading coefficients vanish if and only if the corresponding interpolani to a related function vanishes at given points outside the unit disc. The result is then extended to simultaneous Hermite-Pade interpolation to a finite set of functions.     

TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH

Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree decomposition. In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.     

A refinement about estimation of expansion coefficients for normalized biholomorphic mappings

A refining estimation of homogeneous expansion for / is discussed, where f belongs to a subclass of all normalized biholomorphic mappings defined on the unit polydisk in Cn or the unit ball in complex Banach spaces, and x = 0 is a zero of order k 1 of f(x)-x. Moreover, an estimation of homogeneous expansion for subordinate mappings defined on the unit ball in complex Banach spaces is also given.     

MODIFIED LEAST SQUARE METHOD ON COMPUTING DIRICHLET PROBLEMS

The singularity theory of dynamical systems is linked to the numerical computation of boundary value problems of differential equations. It turns out to be a modified least square method for a calculation of variational problem defined on Ck(Ω), in which the base functions are polynomials and the computation of problems is transferred to compute the coefficients of the base functions. The theoretical treatment and some simple examples are provided for understanding the modification procedure of the methods. A modified least square method on difference scheme is introduced with a general matrix form of dynamical systems. We emphasize the simplicity of the algorithm and only use Euler algorithm to compute initial value problems of ODEs. A better algorithm is needed to reduce the stiffness of ODEs.     

A CAPACITY EXPANSION PROBLEM WITH BUDGET CONSTRAINT AND BOTTLENECK LIMITATION

1 IntroductionIn [2] tl1e authors considered a type of coustrained maximim capacity path problem whichcan be described briefly as: kuowing the costs for expallding one unit of capacity along differentedge8 of a l1etwork aud the availabIe budget, how to iucrease the caparities of the edges so thattlle capasity between any pair of nodes in the lletwork can be raised unifornily to the maximumextent? As the total cost is a summation of the expansion costs on all edges, this problem i8related to mi…     

Constructive characterizations of (γp,γ)- and (γp,γpr)-trees

Let G = (V,E) be a graph without isolated vertices.A set S V is a domination set of G if every vertex in V - S is adjacent to a vertex in S,that is N[S] = V.The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S C V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in N[S] are observed initially,and (ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed (by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

ON SYMMETRIC SCALAR CURVATURE ON

1.IntroductionGivenacontinuousfunctionRonthestandardsphereS',itisaninterestingproblemwhetherRcanbethescalarcurvatureofsomemetricgwhichispointwiseconformaltothestandardmetricgoonS2.Ifwesetg~e"go,whereuisafunctiononS',theproblemisequivalenttothesolvabilityofthefollowingPDE:--A..u 2--Re"=0,onS2.(l'1)KazdanandWarner[9]pointedoutthatitmaybeinsolvable.Inthelastfewyears,alotofworkhasbeendonetosolveproblem(l.l),especiallywhenRpossessessomekindsofsymmetries.AfterthepioneerworkduetoMoser[lo]forthe…     

关于复平面有界闭集上的有理函数逼近

给出了复平面有界闭集的壳与有理函数的可逼近性之间的关系定理。     

BOUNDS ON COINCIDENCE INDICES ON NON-ORIENTABLE SURFACES

§ 1 . IntroductionQuestions about bounds for indices ?rst appeared in the ?xed point context. The ?rstresults appeared in studies of surface homeomorphisms (see [13, 18, 19]). In [12, 14] and[15] some results about bounds for Nielsen ?xed point class ind…     

限制参数空间上的Fiducial推断

给出了在限制参数空间上,利用Fiducial方法求参数的区间估计的一般方法,并且讨论了一些常见的典型问题,结果表明所得的区间估计是合理的．另外,本文还证明了在限制参数空间上,刻度族和位置族中参数的条件Fiducial分布与无信息先验的Bayes 后验分布一致,推广了Lindely的结论．     

关于曲面无穷小等距的两个定理

本文研究了一类曲面的无穷小Ⅰ（Ⅲ）—等距，得到了两个整体定理，并由此证明了在适当的边界条件下，特殊Ｗｅｉｎｇａｒｔｅｎ曲面Ｍ的无穷小Ⅰ（Ⅲ）—等距Φ是关于Ｍ的无穷小刚体运动。     

ON BAND IRREDUCIBLE OPERATORS ON BANACH LATTICES

Abstract

In this note we prove an extension of B. de Pagter's theorem (positive, compact, irreducible operators on Banach lattices are not quasi-nilpotent) for positive, band irreducible operators on Banach lattices satisfying some additional conditions.     

两个安全第一思想模型的比较分析

针对投资者可能的投资需求确立了基于安全第一思想下两个相近的投资目标:1、极大化投资末期总收益率超过给定水平α的概率;2、极小化投资末期总收益率与给定水平α的距离.并分别就这两个目标建立了优化决策模型,得到了模型解析解,最后对两个模型结果进行了比较分析和经济解释.     

关于余极限范畴(英文)

本文研究了余极限范畴.利用余完备Abel范畴的定义,证明了余完备Abel范畴A的余极限范畴Acl是余完备的Abel范畴,并得到一类等价于模范畴的余极限范畴,从而推广了文献[9]中的一些结果.     

关于k-映射

本文给出度量空间ｋ－映象的一些新的特征。证明了ｋ－映射保持一些具有某种特定性质的点可数覆盖的空间。     

关于D-空间

本文研究了用邻域对应定义的空间类.利用构造性的方法,证明了有限多个狭义拟仿紧空间的并是aD-空间及λ-半层空间是D-空间,得到了拓扑空间是aD-空间或D-空间的充分条件,一般化了已有的相应结果.