Robustness of optimal designs for correlated random variables

Suppose that Y = (Y_i) is a normal random vector with mean Xb and covariance σ²I_n, where b is a p-dimensional vector (b_j), X = (X_ij) is an n × p matrix with X_ij ∈ {−1, 1}; this corresponds to a factorial design with −1, 1 representing low or high level respectively, or corresponds to a weighing design with −1, 1 representing an object j with weight b_j placed on the left and right of a chemical balance respectively. E-optimal designs Z are chosen that are robust in the sense that they remain E-optimal when the covariance of Y_i, Y_i′ is ρ > 0 for i ≠ i′. Within a smaller class of designs similar results are obtained with respect to a general class of optimality criteria which include the A- and D-criteria.     

Generalized Gaussian quadrature rules over two-dimensional regions with linear sides

This paper presents a generalized Gaussian quadrature method for numerical integration over triangular, parallelogram and quadrilateral elements with linear sides. In order to derive the quadrature rule, a general transformation of the regions, R₁ = {(x, y)∣a ? x ? b, g(x) ? y ? h(x)} and R₂ = {(x, y)∣a ? y ? b, g(y) ? x ? h(y)}, where g(x), h(x), g(y) and h(y) are linear functions, is given from (x, y) space to a square in (ξ, η) space, S: {(ξ, η)∣0 ? ξ ? 1, 0 ? η ? 1}. Generlized Gaussian quadrature nodes and weights introduced by Ma et.al. in 1997 are used in the product formula presented in this paper to evaluate the integral over S, as it is proved to give more accurate results than the classical Gauss Legendre nodes and weights. The method can be used to integrate a wide class of functions including smooth functions and functions with end-point singularities, over any two-dimensional region, bounded by linear sides. The performance of the method is illustrated for different functions over different two-dimensional regions with numerical examples.     

Minimal ranks of some quaternion matrix expressions with applications

Suppose that p(X, Y) = A − BX − X^(∗)B^(∗) − CYC^(∗) and q(X, Y) = A − BX + X^(∗)B^(∗) − CYC^(∗) are quaternion matrix expressions, where A is persymmetric or perskew-symmetric. We in this paper derive the minimal rank formula of p(X, Y) with respect to pair of matrices X and Y = Y^(∗), and the minimal rank formula of q(X, Y) with respect to pair of matrices X and Y = −Y^(∗). As applications, we establish some necessary and sufficient conditions for the existence of the general (persymmetric or perskew-symmetric) solutions to some well-known linear quaternion matrix equations. The expressions are also given for the corresponding general solutions of the matrix equations when the solvability conditions are satisfied. At the same time, some useful consequences are also developed.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

Eigenvector-free solutions to AX = B with PX = XP and X = sX constraints

The matrix equation AX = B with PX = XP and X^H = sX constraints is considered, where P is a given Hermitian involutory matrix and s = ±1. By an eigenvalue decomposition of P, we equivalently transform the constrained problem to two well-known constrained problems and represent the solutions in terms of the eigenvectors of P. Using Moore-Penrose generalized inverses of the products generated by matrices A, B and P, the involved eigenvectors can be released and eigenvector-free formulas of the general solutions are presented. Similar strategy is applied to the equations AX = B, XC = D with the same constraints.     

Eigenvalues and the One-Dimensional p-Laplacian

We consider the boundary value problem (?_p(u′))′ + λF(t, u) = 0, with p > 1, t ∈ (0, 1), u(0) = u(1) = 0, and with λ > 0. The value of λ is chosen so that the boundary value problem has a positive solution. In addition, we derive an explicit interval for λ such that, for any λ in this interval, the existence of a positive solution to the boundary value problem is guaranteed. In addition, the existence of two positive solutions for λ in an appropriate interval is also discussed.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Stable periodic traveling waves for a predator-prey model with non-constant death rate and delay

In this paper we will consider a predator-prey model with a non-constant death rate and distributed delay, described by a partial integro-differential system. The main goal of this work is to prove that the partial integro-differential system has periodic orbitally asymptotically stable solutions in the form of periodic traveling waves; i.e. N(x, t) = N(σt − μ · x), P(x, t) = P(σt − μ · x), where σ > 0 is the angular frequency and μ is the vector number of the plane wave, which propagates in the direction of the vector μ with speed c = σ/∥μ∥; and N(x, t) and P(x, t) are the spatial population densities of the prey and the predator species, respectively. In order to achieve our goal we will use singular perturbation’s techniques.     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

The eigenvalue distribution on Schur complements of H-matrices

The paper studies the eigenvalue distribution of some special matrices. Tong in Theorem 1.2 of [Wen-ting Tong, On the distribution of eigenvalues of some matrices, Acta Math. Sinica (China), 20 (4) (1977) 273-275] gives conditions for an n × n matrix A ∈ SD_n ∪ ID_n to have |J_R+(A)| eigenvalues with positive real part, and |J_R-(A)| eigenvalues with negative real part. A counter-example is given in this paper to show that the conditions of the theorem are not true. A corrected condition is then proposed under which the conclusion of the theorem holds. Then the corrected condition is applied to establish some results about the eigenvalue distribution of the Schur complements of H-matrices with complex diagonal entries. Several conditions on the n × n matrix A and the subset α ⊆ N = {1, 2, … , n} are presented such that the Schur complement matrix A/α of the matrix A has eigenvalues with positive real part and eigenvalues with negative real part.     

Linear transformations that are tridiagonal with respect to both eigenbases of a Leonard pair

Let V denote a vector space with finite positive dimension. We consider a pair of linear transformations A : V → V and A^∗ : V → V that satisfy (i) and (ii) below:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

We call such a pair a Leonard pair on V. Let X denote the set of linear transformations X : V → V such that the matrix representing X with respect to the basis (i) is tridiagonal and the matrix representing X with respect to the basis (ii) is tridiagonal. We show that X is spanned by

     

Generalized knight’s tour on 3D chessboards

In [G.L. Chia, Siew-Hui Ong, Generalized knight’s tours on rectangular chessboards, Discrete Applied Mathematics 150 (2005) 80-98], Chia and Ong proposed the notion of the generalized knight’s tour problem (GKTP). In this paper, we address the 3D GKTP, that is, the GKTP on 3D chessboards of size L×M×N, where L≤M≤N. We begin by presenting several sufficient conditions for a 3D chessboard not to admit a closed or open generalized knight’s tour (GKT) with given move patterns. Then, we turn our attention to the 3D GKTP with (1, 2, 2) move. First, we show that a chessboard of size L×M×N does not have a closed GKT if either (a) L≤2 or L=4, or (b) L=3 and M≤7. Then, we constructively prove that a chessboard of size 3×4s×4t with s≥2and t≥2 must contain a closed GKT.     

Well-posedness and weak rotation limit for the Ostrovsky equation

We consider the Cauchy problem of the Ostrovsky equation. We first prove the time local well-posedness in the anisotropic Sobolev space Hs,a with s>−a/2−3/4 and 0?a?−1 by the Fourier restriction norm method. This result include the time local well-posedness in Hs with s>−3/4 for both positive and negative dissipation, namely for both βγ>0 and βγ<0. We next consider the weak rotation limit. We prove that the solution of the Ostrovsky equation converges to the solution of the KdV equation when the rotation parameter γ goes to 0 and the initial data of the KdV equation is in L². To show this result, we prove a bilinear estimate which is uniform with respect to γ.     

On some special codes over Fp + uFp + uFp

We define a new map between codes over F_p + uF_p + u²F_p and F_p which is different to that defined in [2]. It is proved that the image of the linear cyclic code over the commutative ring F_p + uF_p + u²F_p with length n under this map is a distance-invariant quasi-cyclic code of index p² with length p²n over F_p. Moreover, it is proved that, if (n, p) = 1, then every code with length p²n over F_p which is the image of a linear (1 − u²)-cyclic code with length n over F_p + uF_p + u²F_p under this map is permutation equivalent to a quasi-cyclic code of index p².     

Essential spectra of some matrix operators and application to two-group transport operators with general boundary conditions

In this article we investigate the essential spectra of a 2×2 block operator matrix on a Banach space. Furthermore, we apply the obtained results to determine the essential spectra of two-group transport operators with general boundary conditions in the Banach space Lp([−a,a]×[−1,1])×Lp([−a,a]×[−1,1]), a>0.     

Small Entire Functions with Infinite Growth Index

In this paper, we prove that given μ > 0 there exists a dense linear manifold M of entire functions, such that,[formula]for every f ∈ M and l straight line and with infinite growth index for all non-null functions of M. Moreover, every non-null function of M has exactly 2([2μ] + 1) Julia directions. And if l is a straight line that does not contain a Julia line, then for every f ∈ M[formula]and for j ≥ 1, f^(j) is bounded and integrable with respect to the length measure on l and ∫_lf^(j) = 0.     

Two-worker blocking congestion model with walk speed m in a no-passing circular passage system

This paper introduces a blocking model and closed-form expression of two workers traveling with walk speed m (m = integer) in a no-passing circular-passage system of n stations and assuming n = m + 2, 2m + 2, …. We develop a Discrete-Timed Markov Chain (DTMC) model to capture the workers’ changes of walk, pick, and blocked states, and quantify the throughput loss from blocking congestion by deriving a steady state probability in a closed-form expression. We validate the model with a simulation study. Additional simulation comparisons show that the proposed throughput model gives a good approximation of a general-sized system of n stations (i.e., n > 2), a practical walk speed system of real number m (i.e., m ? 1), and a bucket brigade order picking application.     

Krull’s theory for the double gamma function

The Barnes’ G-function G(x) = 1/Γ₂, satisfies the functional equation logG(x + 1) − logG(x) = logΓ(x). We complement W. Krull’s work in Bemerkungen zur Differenzengleichung g(x + 1) − g(x) = φ(x), Math. Nachrichten 1 (1948), 365-376 with additional results that yield a different characterization of the function G, new expansions and sharp bounds for G on x > 0 in terms of Gamma and Digamma functions, a new expansion for the Gamma function and summation formulae with Polygamma functions.