Bayesian linear prediction in finite populations

In this paper, Bayesian linear prediction of the total of a finite population is considered in situations where the observation error variance is parameter dependent. Connections with least squares prediction (Royall (1976, J. Amer. Statist. Assoc., 71, 657–664)) in mixed linear models (Theil (1971, Principles of Econometrics, Wiley, New York)), are established. Extensions to the case of dynamic (state dependent) superpopulation models are also proposed.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Randomized broadcast in networks

In this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in the maintenance of replicated databases.     

On Linear Representations of Analytic Moufang Loops

Mathematical Notes -     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

Minimum Distance Between the Faces of Two Convex Polyhedra: A Sufficient Condition

The problem of finding the Euclidean distance between two convex polyhedra can be reduced to the combinatorial optimization problem of finding the minimum distance between their faces. This paper presents a global optimality criterion for this problem. An algorithm (QLDPA) for the fast computation of the distance between convex and bounded polyhedra is proposed as an application of it. Computer experiments show its fast performance, especially when the total number of vertices is large.     

The Linear Rational Pseudospectral Method with Preassigned Poles

We present a linear rational pseudospectral (collocation) method with preassigned poles for solving boundary value problems. It consists in attaching poles to the trial polynomial so as to make it a rational interpolant. Its convergence is proved by transforming the problem into an associated boundary value problem. Numerical examples demonstrate that the rational pseudospectral method is often more efficient than the polynomial method.     

Two-Step High Order Starting Values for Implicit Runge–Kutta Methods

In this article a simple form of expressing and studying the order conditions to be satisfied by starting algorithms for Runge–Kutta methods, which use information from the two previous steps is presented. In particular, starting algorithms of highest order for Runge–Kutta–Gauss methods up to seven stages are derived. Some numerical experiments with Hamiltonian systems to compare the behaviour of the new starting algorithms with other existing ones are presented.     

Robust Output Tracking Control of an Uncertain Linear System via a Modified Optimal Linear-Quadratic Method

This study investigates the robust output tracking problem for a class of uncertain linear systems. The uncertainties are assumed to be time invariant and to satisfy the matching conditions. According to the selected nominal parameters, an optimal solution with a prescribed degree of stability is determined. Then, an auxiliary input via the use of an adapting factor, connected to the nominal optimal control, is introduced to guarantee the robustness and prescribed degree of stability for the output tracking control of the uncertain linear systems. This method is very simple and effective and can reject bounded uncertainties imposed on the states. A maglev vehicle model example is given to show its effectiveness.