Termination Criteria for Linear Problems

We study two termination criteria which are used in computational practice. They are analyzed for linear problems in the average case setting. It is assumed that arbitrary continuous linear functionals can be computed and consecutive approximations are chosen in the best possible way. The first termination criterion is satisfied if the difference between two consecutive approximations becomes less than a certain bound τ. We prove that the first termination criterion gives satisfactory results only for some cases. The second termination criterion is satisfied if two consecutive differences between consecutive approximations become less than τ. We prove that the second termination criterion gives satisfactory results for all cases.     

Classification of Certain Class of Ordinary Differential Equations of the First Order

We study problem of global classification of ordinary differential equations with the linear-fractional right-hand side with rational coefficients with respect to a symmetry group. We find the field of differential invariants and obtain the equivalence criterion for two such equations. We adduce certain examples for applying of this criterion. These examples were obtained by means of computer.     

On factorization of the characteristic quasipolynomial of a system of linear differential equations with delay

We establish a factorization criterion for the characteristic quasipolynomial of a system of two linear autonomous differential equations with delay. On the base of this criterion we obtain several criteria of the asymptotic stability.     

Criteria of motivic equivalence for quadratic forms and central simple algebras

We give a short, elementary, and characteristic independent proof of the criterion for motivic isomorphism of two projective quadrics discovered by A. Vishik [24]. We also give a criterion for motivic isomorphism of two Severi-Brauer varieties. Received: 1 February 1999 / Published online: 8 May 2000     

Comparison and bounds for functionals of future lifetimes consistent with life tables

We derive a new crossing criterion of hazard rates to identify a stochastic order relation between two random variables. We apply this crossing criterion in the context of life tables to derive stochastic ordering results among three families of fractional age assumptions: the family of linear force of mortality functions, the family of quadratic survival functions and the power family. Further, this criterion is used to derive tight bounds for functionals of future lifetimes that exhibit an increasing force of mortality with given one-year survival probabilities. Numerical examples illustrate our findings.     

Symmetric Framelets

We study tight wavelet frames associated with symmetric compactly supported refinable functions, which are obtained with the unitary extension principle . We give a criterion for the existence of two symmetric or antisymmetric compactly supported framelets. All refinable masks of length up to 6 satisfying this criterion are found.     

On the Stability of Equilibria in Two-Degrees-of- Freedom Hamiltonian Systems Under Resonances

We consider the problem of stability of equilibrium points in Hamiltonian systems of two degrees of freedom under resonances. Determining the stability or instability is based on a geometrical criterion based on how two surfaces, related with the normal form, intersect one another. The equivalence of this criterion with a result of Cabral and Meyer is proved. With this geometrical procedure, the hypothesis may be extended to more general cases.     

Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work

We study the scheduling problem with a common due date on two parallel identical machines and the total early work criterion. The problem is known to be NP-hard. We prove a few dominance properties of optimal solutions of this problem. Their proposal was inspired by the results of some auxiliary computational experiments. Test were performed with the dynamic programming algorithm and list algorithms. Then, we propose the polynomial time approximation scheme, based on structuring problem input. Moreover, we discuss the relationship between the early work criterion and the related late work criterion. We compare the computational complexity and approximability of scheduling problems with both mentioned objective functions.     

Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information

We deal with zero-sum two-player stochastic games with perfect information. We propose two algorithms to find the uniform optimal strategies and one method to compute the optimality range of discount factors. We prove the convergence in finite time for one algorithm. The uniform optimal strategies are also optimal for the long run average criterion and, in transient games, for the undiscounted criterion as well.     

Lyapunov direct method in the analysis of Lagrange instability with respect to part of the variables

We obtain a sufficient condition using two Lyapunov functions for the Lagrange instability with respect to part of the variables. We also obtain another sufficient condition for the Lagrange instability with respect to part of the variables; this condition uses one Lyapunov function and is an analog of the Chetaev theorem on the instability with respect to part of the variables. If the considered part of the variables coincides with the set of all variables, then the sufficient criterion with one Lyapunov function is a corollary of the sufficient criterion with two Lyapunov functions.     

An information criterion for model selection with missing data via complete-data divergence

We derive an information criterion to select a parametric model of complete-data distribution when only incomplete or partially observed data are available. Compared with AIC, our new criterion has an additional penalty term for missing data, which is expressed by the Fisher information matrices of complete data and incomplete data. We prove that our criterion is an asymptotically unbiased estimator of complete-data divergence, namely the expected Kullback–Leibler divergence between the true distribution and the estimated distribution for complete data, whereas AIC is that for the incomplete data. The additional penalty term of our criterion for missing data turns out to be only half the value of that in previously proposed information criteria PDIO and AICcd. The difference in the penalty term is attributed to the fact that our criterion is derived under a weaker assumption. A simulation study with the weaker assumption shows that our criterion is unbiased while the other two criteria are biased. In addition, we review the geometrical view of alternating minimizations of the EM algorithm. This geometrical view plays an important role in deriving our new criterion.     

A birational embedding with two Galois points for quotient curves

A criterion for the existence of a birational embedding with two Galois points for quotient curves is presented. We apply our criterion to several curves, for example, some cyclic subcovers of the Giulietti–Korchmáros curve or of the curves constructed by Skabelund. New examples of plane curves with two Galois points are described, as plane models of such quotient curves.     

Resource pooling in congested networks: proportional fairness and product form

We review two areas of recent research linking proportional fairness with product form networks. The areas concern, respectively, the heavy traffic and the large deviations limiting regimes for the stationary distribution of a flow model, where the flow model is a stochastic process representing the randomly varying number of document transfers present in a network sharing capacity according to the proportional fairness criterion. In these two regimes we postulate the limiting form of the stationary distribution, by comparison with several variants of the fairness criterion. We outline how product form results can help provide insight into the performance consequences of resource pooling.     

When do several linear operators share an invariant cone?

We establish a criterion for a finite family of matrices to possess a common invariant cone. The criterion reduces the problem of existence of an invariant cone to equality of two special numbers that depend on the family. In spite of theoretical simplicity, the practical use of the criterion may be difficult. We show that the problem of existence of a common invariant cone for four matrices with integral entries is algorithmically undecidable. Corollaries of the criterion, which give sufficient and necessary conditions, are derived. Finally, we introduce a “co-directional number” of several matrices. We prove that this parameter is close to zero iff there is a small perturbation of matrices, after which they get an invariant cone. An algorithm for its computation is presented.     

On a generalized Camassa–Holm equation with the flow generated by velocity and its gradient

In this paper, we consider a generalized Camassa–Holm equation with the flow generated by the vector field and its gradient. We first establish the local well-posedness of equation in the sense of Hadamard in both critical Besov spaces and supercritical Besov spaces. Then we gain a blow-up criterion. Under a sign condition we reach the sign-preserved property and a precise blow-up criterion. Applying this precise criterion we finally present two blow-up results and the precise blow-up rate for strong solutions to equation.     

Semiparametric Approximation Methods in Multivariate Model Selection

In this paper we propose a cross-validation selection criterion to determine asymptotically the correct model among the family of all possible partially linear models when the underlying model is a partially linear model. We establish the asymptotic consistency of the criterion. In addition, the criterion is illustrated using two real sets of data.     

Inner Homomorphisms and Positive-Conditional Terms

We establish the criterion for two finite or uniformly locally finite algebras of a finite signature to be positive-conditionally rational equivalent (in terms of semigroups of inner homomorphisms of these algebras) and the criterion for two finite algebras to be strongly similar (in terms of expanded semigroups of inner homomorphisms of those algebras).     

主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

Cluster-tilted algebras and slices

We give a criterion allowing to verify whether or not two tilted algebras have the same relation-extension (thus correspond to the same cluster-tilted algebra). This criterion is in terms of a combinatorial configuration in the Auslander–Reiten quiver of the cluster-tilted algebra, which we call local slice.     

Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance

We establish an ordering criterion for the asymptotic variances of two consistent Markov chain Monte Carlo (MCMC) estimators: an importance sampling (IS) estimator, based on an approximate reversible chain and subsequent IS weighting, and a standard MCMC estimator, based on an exact reversible chain. Essentially, we relax the criterion of the Peskun type covariance ordering by considering two different invariant probabilities, and obtain, in place of a strict ordering of asymptotic variances, a bound of the asymptotic variance of IS by that of the direct MCMC. Simple examples show that IS can have arbitrarily better or worse asymptotic variance than Metropolis–Hastings and delayed-acceptance (DA) MCMC. Our ordering implies that IS is guaranteed to be competitive up to a factor depending on the supremum of the (marginal) IS weight. We elaborate upon the criterion in case of unbiased estimators as part of an auxiliary variable framework. We show how the criterion implies asymptotic variance guarantees for IS in terms of pseudo-marginal (PM) and DA corrections, essentially if the ratio of exact and approximate likelihoods is bounded. We also show that convergence of the IS chain can be less affected by unbounded high-variance unbiased estimators than PM and DA chains.