Local Particles Numbers in Critical Branching Random Walk

Critical catalytic branching random walk on an integer lattice ? ^d is investigated for all d∈?. The branching may occur at the origin only and the start point is arbitrary. The asymptotic behavior, as time grows to infinity, is determined for the mean local particles numbers. The same problem is solved for the probability of the presence of particles at a fixed lattice point. Moreover, the Yaglom type limit theorem is established for the local number of particles. Our analysis involves construction of an auxiliary Bellman–Harris branching process with six types of particles. The proofs employ the asymptotic properties of the (improper) c.d.f. of hitting times with taboo. The latter notion was recently introduced by the author for a non-branching random walk on ? ^d .     

The Clique Complex and Hypergraph Matching

The width of a hypergraph is the minimal for which there exist such that for any , for some . The matching width of is the minimal such that for any matching there exist such that for any , for some . The following extension of the Aharoni-Haxell matching Theorem [3] is proved: Let be a family of hypergraphs such that for each either or , then there exists a matching such that for all . This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the Nerve Theorem. Received June 14, 1999     

The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734–737. Presented by Academician S.N. Vasil’ev February 9, 2009 The article was translated by the authors.     

Monotonicity of the search number in the Golovach problem

The Golovach problem, also known as the ɛ-search problem, is as follows. A team of pursuers pursues an evader on a topological graph. The objective of the pursuers is to catch the evader, that is, approach the evader to a distance not exceeding a given nonnegative number ɛ. It is assumed that the evader is invisible to the pursuers and is fully informed beforehand about the search program of the pursuers. The problem is to find the ɛ-search number, i.e., the least number of pursuers sufficient for capturing the evader. Graphs with monotone ɛ-search number are studied; the ɛ-search number of a graph G is said to be monotone if it is not exceeded by the ɛ-search numbers of all connected subgraphs H of G. It is known that the ɛ-search number of any tree is monotone for all nonnegative ɛ. The edgesearch number, which is equal to the 0-search number, is monotone for all connected subgraphs of an arbitrary graph. A sufficient monotonicity condition for the ɛ-search number of any graph is obtained. This result is improved in the case of complete subgraphs. The Golovach function is constructed for graphs obtained by removing one edge from complete graphs with unit edges.     

Dual simplex method for GUB problems

The dual simplex method for generalized upper bound (GUB) problems is presented. One of the major operations in the dual simplex method is to update the elements of therth row, wherer is the index for the leaving basic variable. Those updated elements are used for the ratio test to determine the entering basic variabble. A very simple formula for therth row update for the dual simplex method for a GUB problem is derived, which is similar to the formula for the standard linear program. This derivation is based on the change key operation, which is to exchange the key column and its counterpart in the nonkey section. The change key operation is possible because of a theorem that guarantees the existence of such a counterpart.     

Numerical convergence on adaptive grids for control volume methods

An adaptive technique for control‐volume methods applied to second order elliptic equations in two dimensions is presented. The discretization method applies to initially Cartesian grids aligned with the principal directions of the conductivity tensor. The convergence behavior of this method is investigated numerically. For solutions with low Sobolev regularity, the found L² convergence order is two for the potential and one for the flow density. The system of linear equations is better conditioned for the adaptive grids than for uniform grids. The test runs indicate that a pure flux‐based refinement criterion is preferable.© 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Fast verification of solutions of matrix equations

Summary. In this paper, we are concerned with a matrix equation where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations. Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001     

Infinite Matroidal Version of Hall's Matching Theorem

Hall's theorem for bipartite graphs gives a necessary and sufficientcondition for the existence of a matching in a given bipartitegraph. Aharoni and Ziv have generalized the notion of matchabilityto a pair of possibly infinite matroids on the same set andgiven a condition that is sufficient for the matchability ofa given pair (M, W) of finitary matroids, where the matroidM is SCF (a sum of countably many matroids of finite rank).The condition of Aharoni and Ziv is not necessary for matchability.The paper gives a condition that is necessary for the existenceof a matching for any pair of matroids (not necessarily finitary)and is sufficient for any pair (M, W) of finitary matroids,where the matroid M is SCF.     

On energy estimates for second order hyperbolic equations with Levi conditions for higher order regularity

We consider energy estimates for second order homogeneous hyperbolic equations with time dependent coefficients. The property of energy conservation, which holds in the case of constant coefficients, does not hold in general for variable coefficients; in fact, the energy can be unbounded as t → ∞ in this case. The conditions to the coefficients for the generalized energy conservation (GEC), which is an equivalence of the energy uniformly with respect to time, has been studied precisely for wave type equations, that is, only the propagation speed is variable. However, it is not true that the same conditions to the coefficients conclude (GEC) for general homogeneous hyperbolic equations. The main purpose of this paper is to give additional conditions to the coefficients which provide (GEC); they will be called as C ^k -type Levi conditions due to the essentially same meaning of usual Levi condition for the well-posedness of weakly hyperbolic equations.     

The Integral Equation Method and the Neumann Problem for the Poisson Equation on NTA Domains

The Neumann problem for the Poisson equation is studied on a general open subset G of the Euclidean space. The right-hand side is a distribution F supported on the closure of G. It is shown that a solution is the Newton potential corresponding to a distribution B ∈ε (clG), where ε(clG) is the set of all distributions with finite energy supported on the closure of G. The solution is looked for in this form and the original problem reduces to the integral equation TB = F. If the equation TB = F is solvable, then the solution is constructed by the Neumann series. The necessary and sufficient conditions for the solvability of the equation TB = F is given for NTA domains with compact boundary. The research was supported by the Academy of Sciences of the Czech Republic, Institutional Research Plan No. AV0Z10190503.     

Identification of a dissipation coefficient by a variational method

A generalized inverse problem for the identification of the absorption coefficient for a hyperbolic system is considered. The well-posedness of the problem is examined. It is proved that the regular part of the solution is an L ₂ function, which reduces the inverse problem to minimizing the error functional. The gradient of the functional is determined in explicit form from the adjoint problem, and approximate formulas for its calculation are derived. A regularization algorithm for the solution of the inverse problem is considered. Numerical results obtained for various excitation sources are displayed.     

Perishable Inventory System at Service Facilities with N Policy

Abstract

This article presents a perishable stochastic inventory system under continuous review at a service facility in which the waiting hall for customers is of finite size M. The service starts only when the customer level reaches N (< M), once the server has become idle for want of customers. The maximum storage capacity is fixed as S. It is assumed that demand for the commodity is of unit size. The arrivals of customers to the service station form a Poisson process with parameter λ. The individual customer is issued a demanded item after a random service time, which is distributed as negative exponential. The items of inventory have exponential life times. It is also assumed that lead time for the reorders is distributed as exponential and is independent of the service time distribution. The demands that occur during stock out periods are lost.The joint probability distribution of the number of customers in the system and the inventory levels is obtained in steady state case. Some measures of system performance in the steady state are derived. The results are illustrated with numerical examples.     

A numerical technique based on B-spline for a class of time-fractional diffusion equation

This paper presents an efficient numerical technique for solving a class of time-fractional diffusion equation. The time-fractional derivative is described in the Caputo form. The L1 scheme is used for discretization of Caputo fractional derivative and a collocation approach based on sextic B-spline basis function is employed for discretization of space variable. The unconditional stability of the fully-discrete scheme is analyzed. Two numerical examples are considered to demonstrate the accuracy and applicability of our scheme. The proposed scheme is shown to be sixth order accuracy with respect to space variable and (2 − α)-th order accuracy with respect to time variable, where α is the order of temporal fractional derivative. The numerical results obtained are compared with other existing numerical methods to justify the advantage of present method. The CPU time for the proposed scheme is provided.     

Das Anfangs-Randwertproblem eines dünnen Profils in kompressibler Unterschallströmung

Summary The initial boundary value problem of a thin profile in a compressible subsonic flow is investigated, being important for the gust problem. Existence and uniqueness of the solution are shown. By a generalizedWiener-Hopf-equation, the solution is reduced to the solution of a system of integro-differential equations for the downwashes in the profile plane. This system can be solved exactly by an iterative calculation of integrals for any value of timet>0. Finally, for smallt>0, the indicial-admittance function for vertical translation is found and is compared with a result given byLomax [6]. The asymptotic case for larget>0 will be investigated in a later paper.     

The Rayleigh–Stokes problem for an edge in a generalized Oldroyd-B fluid

The velocity field corresponding to the Rayleigh–Stokes problem for an edge, in an incompressible generalized Oldroyd-B fluid has been established by means of the double Fourier sine and Laplace transforms. The fractional calculus approach is used in the constitutive relationship of the fluid model. The obtained solution, written in terms of the generalized G-functions, is presented as a sum of the Newtonian solution and the corresponding non-Newtonian contribution. The solution for generalized Maxwell fluids, as well as those for ordinary Maxwell and Oldroyd-B fluids, performing the same motion, is obtained as a limiting case of the present solution. This solution can be also specialized to give the similar solution for generalized second grade fluids. However, for simplicity, a new and simpler exact solution is established for these fluids. For β → 1, this last solution reduces to a previous solution obtained by a different technique.     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

The value function of an integer program

We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.     

Design Adaptive Nearest Neighbor Regression Estimation

This paper deals with nonparametric regression estimation under arbitrary sampling with an unknown distribution. The effect of the distribution of the design, which is a nuisance parameter, can be eliminated by conditioning. An upper bound for the conditional mean squared error of k−NN estimates leads us to consider an optimal number of neighbors, which is a random function of the sampling. The corresponding estimate can be used for nonasymptotic inference and is also consistent under a minimal recurrence condition. Some deterministic equivalents are found for the random rate of convergence of this optimal estimate, for deterministic and random designs with vanishing or diverging densities. The proposed estimate is rate optimal for standard designs.     

Maximal amplitudes of hyperelliptic solutions of the derivative nonlinear Schrödinger equation

A simple formula is proven for an upper bound for amplitudes of hyperelliptic (finite-gap or N-phase) solutions of the derivative nonlinear Schrödinger equation. The upper bound is sharp, viz, it is attained for some initial conditions. The method used to prove the upper bound is the same method, with necessary modifications, used to prove the corresponding bound for solutions of the focusing NLS equation (Wright OC, III. Sharp upper bound for amplitudes of hyperelliptic solutions of the focusing nonlinear Schrödinger equation. Nonlinearity. 2019;32:1929-1966).