A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

Convergence rates for Markov chain order estimates using EDC criterion

The Efficient Determination Criterion (EDC) generalizes the AIC and BIC criteria and provides a class of consistent estimators for the order of a Markov chain with finite state space. In this note, we derive rates of convergence for the EDC estimates. *Partially supported by CNPq, CAPES/PROCAD, FAPDF/PRONEX, FINATEC and FUNPE/UnB. **Partially supported by CAPES.     

Selection Principles and Sierpinski Sets

We show that a set of real numbers is a Sierpinski set if, and only if, it satisfies a selection property similar to the familiar Menger property.     

Maximin share and minimax envy in fair-division problems

For fair-division or cake-cutting problems with value functions which are normalized positive measures (i.e., the values are probability measures) maximin-share and minimax-envy inequalities are derived for both continuous and discrete measures. The tools used include classical and recent basic convexity results, as well as ad hoc constructions. Examples are given to show that the envy-minimizing criterion is not Pareto optimal, even if the values are mutually absolutely continuous. In the discrete measure case, sufficient conditions are obtained to guarantee the existence of envy-free partitions.     

关于任意随机变量序列泛函的强极限定理

本文在k是固定的正整数，{fn}是R^k 1上的Borel可测函数列时，得到了任意随机变量序列{Xrn≥0}的泛函{fn(Xn-k,…,Xn)}的强极限定理，它是Chung的关于独立随机变量序列的强大数律的推广，作为推论，得到了k重非齐次马尔科夫链的一类强极限定理．     

Capacity Constrained Transit Assignment with Common Lines

This paper proposes the use of absorbing Markov chains to solve the capacity constrained transit network loading problem taking common lines into account. The approach handles congested transit networks, where some passengers will not be able to board because of the absence of sufficient space. The model also handles the common lines problem, where choice of route depends on frequency of arrivals. The mathematical formulation of the problem is presented together with a numerical example. This revised version was published online in July 2006 with corrections to the Cover Date.     

Generalized binomial and negative binomial distributions of order<Emphasis Type="Italic">k</Emphasis> by the<Emphasis Type="Italic">l</Emphasis>-overlapping enumeration scheme

In this paper, we investigate the exact distribution of the waiting time for ther-th ℓ-overlapping occurrence of success-runs of a specified length in a sequence of two state Markov dependent trials. The probability generating functions are derived explicitly, and as asymptotic results, relationships of a negative binomial distribution of orderk and an extended Poisson distribution of orderk are discussed. We provide further insights into the run-related problems from the viewpoint of the ℓ-overlapping enumeration scheme. We also study the exact distribution of the number of ℓ-overlapping occurrences of success-runs in a fixed number of trials and derive the probability generating functions. The present work extends several properties of distributions of orderk and leads us a new type of geneses of the discrete distributions.     

Near-Optimal Controls of Discrete-Time Dynamic Systems Driven by Singularly-Perturbed Markov Chains

This work is devoted to near-optimal controls of large-scale discrete-time nonlinear dynamic systems driven by Markov chains; the underlying problem is to minimize an expected cost function. Our main goal is to reduce the complexity of the underlying systems. To achieve this goal, discrete-time control models under singularly-perturbed Markov chains are introduced. Using a relaxed control representation, our effort is devoted to finding near-optimal controls. Lumping the states in each irreducible class into a single state gives rise to a limit system. Applying near-optimal controls of the limit system to the original system, near-optimal controls of the original system are derived.     

Nonparametric estimation and adaptive control in a class of finite Markov decision chains

We consider a class of Markov decision processes withfinite state and action spaces which, essentially, is determined by the following condition: The state space isirreducible under the action of any stationary policy. However, except by this restriction, the transition law iscompletely unknown to the controller. In this context, we find a set of policies under which thefrequency estimators of the transition law are strongly consistent and then, this result is applied to constructadaptive asymptotically discount-optimal policies.Dedicated to Professor Truman O. Lewis, on the occasion of his sixtieth birthdayThis research was supported in part by the Third World Academy of Sciences (TWAS) under Grant TWAS RG MP 898-152, and in part by the Consejo Nacional de Ciencia y Tecnología (CONACYT) under Grant A128CCOEO550 (MT-2).     

带利息力和干扰的批量索赔一般到达风险模型

本文在经典风险模型的基础上,将索赔到达过程推广为更新过程,索赔可以批量到达,且带有常数利息力和Brown运动干扰项,得到一个新的风险模型,运用Markov骨架过程的方法,得出盈余过程的瞬时分布和生存概率.