Stock cutting to minimize cutting length

In this paper we investigate the following problem: Given two convex P_in, and P_out where P_in is completely contained in P_out, we wish to find a sequence of ‘guillotine cuts’ to cut out P_in from P_out such that the total length of the cutting sequence is minimized. This problem has applications in stock cutting where a particular shape or design (in this case the polygon P_in) needs to be cut out of a given piece of parent material (the polygon P_out) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improve the cutting time required per piece. We first prove some properties of the optimal solution to the problem and then give an approximation scheme for the problem that, given an error range δ, produces a cutting sequence whose total length is atmost δ more than that of the optimal cutting sequence. Then it is shown that this problem has optimal solutions that lie in the algebraic extension of the field that the input data belongs to — hence due to this algebraic nature of the problem, an approximation scheme is the best that can be achieved. Extensions of these results are also studied in the case where the polygons P_in and P_out are non-convex.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

Power convergence of Abel averages

Necessary and sufficient conditions are presented for the Abel averages of discrete and strongly continuous semigroups, T ^k and T _t , to be power convergent in the operator norm in a complex Banach space. These results cover also the case where T is unbounded and the corresponding Abel average is defined by means of the resolvent of T. They complement the classical results by Michael Lin establishing sufficient conditions for the corresponding convergence for a bounded T.     

The matrix geometric mean of parameterized, weighted arithmetic and harmonic means

We define a new family of matrix means {L_μ(ω;A)}_μ∈R where ω and A vary over all positive probability vectors in R^m and m-tuples of positive definite matrices resp. Each of these means interpolates between the weighted harmonic mean (μ=-∞) and the arithmetic mean of the same weight (μ=∞) with L_μ≤L_ν for μ≤ν. Each has a variational characterization as the unique minimizer of the weighted sum for the symmetrized, parameterized Kullback-Leibler divergence. Furthermore, each can be realized as the common limit of the mean iteration by arithmetic and harmonic means (in the unparameterized case), or, more generally, the arithmetic and resolvent means. Other basic typical properties for a multivariable mean are derived.     

Analysis of two-sample truncated data using generalized logistic models

Parallel to Cox's [JRSS B34 (1972) 187-230] proportional hazards model, generalized logistic models have been discussed by Anderson [Bull. Int. Statist. Inst. 48 (1979) 35-53] and others. The essential assumption is that the two densities ratio has a known parametric form. A nice property of this model is that it naturally relates to the logistic regression model for categorical data. In astronomic, demographic, epidemiological, and other studies the variable of interest is often truncated by an associated variable. This paper studies generalized logistic models for the two-sample truncated data problem, where the two lifetime densities ratio is assumed to have the form exp{α+φ(x;β)}. Here φ is a known function of x and β, and the baseline density is unspecified. We develop a semiparametric maximum likelihood method for the case where the two samples have a common truncation distribution. It is shown that inferences for β do not depend the nonparametric components. We also derive an iterative algorithm to maximize the semiparametric likelihood for the general case where different truncation distributions are allowed. We further discuss how to check goodness of fit of the generalized logistic model. The developed methods are illustrated and evaluated using both simulated and real data.     

Recovering a Family of Two-Dimensional Gaussian Variables from the Minimum Process

Suppose that {(X _t, Y _t): t>}0 is a family of two independent Gaussian random variables with means m ₁(t) and m ₂(t) and variances σ ² ₁(t) and σ ² ₂(t). If at every time t>0 the first and second moment of the minimum process X _t∧Y _t are known, are the parameters governing these four moment functions uniquely determined ? We answer this question in the negative for a large class of Gaussian families including the “Brownian” case. Except for some degenerate situation where one variance function dominates the other, in which case the recovery of the parameters is fully successful, the second moment of the minimum process does not provide any additional clues on identifying the parameters.     

Uniqueness and growth of weak solutions to certain linear differential equations in Hilbert space

In this paper, we study, by means of a modification of the weighted energy method, the questions of uniqueness and growth of weak solutions to evolutionary equations of the form u_tt = Mu where M is a symmetric operator and u takes values in a Hilbert space. We show that if the initial energy is negative, then the kinetic and potential energies have exponential growth. This is also the case when the initial energy is nonnegative provided it is not too large and the cosine of the angle between the initial displacement and initial velocity is sufficiently close to one.We also derive a continuous dependence result.     

On-diagonal oscillation of the heat kernels on post-critically finite self-similar fractals

For the canonical heat kernels p _t (x, y) associated with Dirichlet forms on post-critically finite self-similar fractals, e.g. the transition densities (heat kernels) of Brownian motion on affine nested fractals, the non-existence of the limit ${\lim_{t\downarrow 0}t^{d_{s}/2}p_{t}(x,x)}$ is established for a “generic” (in particular, almost every) point x, where d _s denotes the spectral dimension. Furthermore the same is proved for any point x in the case of the d-dimensional standard Sierpinski gasket with d ≥ 2 and the N-polygasket with N ≥ 3 odd, e.g. the pentagasket (N = 5) and the heptagasket (N = 7).     

Recurrence and Transience Criteria for Two Cases of Stable-Like Markov Chains

We give recurrence and transience criteria for two cases of time-homogeneous Markov chains on the real line with transition kernel p(x,dy)=f _x (y?x)?dy, where f _x (y) are probability densities of symmetric distributions and, for large |y|, have a power-law decay with exponent α(x)+1, with α(x)∈(0,2). If f _x (y) is the density of a symmetric α-stable distribution for negative x and the density of a symmetric β-stable distribution for non-negative x, where α,β∈(0,2), then the chain is recurrent if and only if α+β≥2. If the function x?f _x is periodic and if the set {x:α(x)=α ₀:=inf _x∈? α(x)} has positive Lebesgue measure, then, under a uniformity condition on the densities f _x (y) and some mild technical conditions, the chain is recurrent if and only if α ₀≥1.     

Optimal control of capital injections by reinsurance in a diffusion approximation

In this paper we consider a diffusion approximation to a classical risk process, where the claims are reinsured by some reinsurance with deductible b ∈ [0,b?], where b = b? means “no reinsurance” and b = 0 means “full reinsurance”. The cedent can choose an adapted reinsurance strategy (b _t ) _{t ≥0}, i.?e. the deductible can be changed continuously. In addition, the cedent has to inject fresh capital in order to keep the surplus positive. The problem is to minimise the expected discounted cost over all admissible reinsurance strategies. We find an explicit expression for the value function and the optimal strategy using the Hamilton–Jacobi–Bellman approach. Some examples illustrate the method.     

Vanishing electron mass limit in the bipolar Euler–Poisson system

The bipolar Euler–Poisson system in physics consists of the conservation laws for the electron and ion densities and their current densities, coupled with the Poisson equation for the electrostatic potential. The limit of vanishing ratio of the electron mass to the ion mass in the $n$-dimensional flat torus is proved in the case of well prepared initial data. The limiting system is composed of two separated equations, where the equation for electron is the incompressible Euler equation with damping, which means physically that the evolution for electrons and ions can be treated as separated motions in the small ratio case.     

Application of the problem of moments to derive bounds on integrals with integral constraints

Recently a lot of results (for a review see Goovaerts et al. (1983)) have been obtained for bounds on stop-loss premiums in case of incomplete information on the claim distribution.As a consequence some extremal distributions (depending on the retention limit) have been characterized. The extremal distributions for the stop-loss ordering in case of fixed values of the retention limit are obtained by means of deep results from the theory of convex analysis. In the present contribution it is shown, by means of some results from the problem of moments, how bounds on integrals with integral constraints can be obtained. We assume only the knowledge of the moments μ₀, μ₁, …, μ_n.     

Distribution-free consistency of kernel non-parametric M-estimators

We prove that in the case of independent and identically distributed random vectors (X_i,Y_i) a class of kernel type M-estimators is universally and strongly consistent for conditional M-functionals. The term universal means that the strong consistency holds for all joint probability distributions of (X,Y). The conditional M-functional minimizes (2.2) for almost every x. In the case M(y)=|y| the conditional M-functional coincides with the L₁-functional and with the conditional median.     

Convergence of Double Walsh-Fourier Series and Hardy Spaces

It is proved that the maximal operator of the Marczinkiewicz-Fejér meams of a double Walsh-Fourier series is bounded from the two-dimensional dyadic martingale Hardy space H _p to L _p (2/3<p<∞) and is of weak type (1,1). As a consequence we obtain that the Marczinkiewicz-Fejér means of a function f∈L ₁ converge a.e. to the function in question. Moreover, we prove that these means are uniformly bounded on H _p whenever 2/3<p<∞. Thus, in case f∈H _p , the Marczinkiewicz-Fejér means conv f in H _p norm. The same results are proved for the conjugate means, too.     

Graphs Satisfying a Richness Condition and One Concerning Forbidden Subgraphs

We characterize several classes of graphs which satify a richness condition (R) and a condition (F) which concerns forbidden subgraphs. In particular we treat the case where (R) is: Each two vertices have a common neighbor. And this in combination with (F): G has no 5-circle C ₅ resp. no 6-circle C ₆ as subgraph. Another result deals with the case where (R) and (F) concern existence or non-existence of circles C _n .     

The symmetric D ω -semi-classical orthogonal polynomials of class one

We give the system of Laguerre–Freud equations associated with the D _ω -semi-classical functionals of class one, where D _ω is the divided difference operator. This system is solved in the symmetric case. There are essentially two canonical cases. The corresponding integral representations are given.     

Approximation of isolated eigenvalues of general singular ordinary differential operators

Let A be a self-adjoint operator defined by a general singular ordinary differential expression τ on an interval (a, b), ? ∞ ≤ a < b ≤ ∞. We show that isolated eigenvalues in any gap of the essential spectrum of A are exactly the limits of eigenvalues of suitably chosen self-adjoint realizations A_n of τ on subintervals (a_n, b_n) of (a, b) with a_n → a, b_n → b. This means that eigenvalues of singular ordinary differential operators can be approximated by eigenvalues of regular operators. In the course of the proof we extend a result, which is well known for quasiregular differential expressions, to the general case: If the spectrum of A is not the whole real line, then the boundary conditions needed to define A can be given using solutions of (τ ? λ)u = 0, where λ is contained in the regularity domain of the minimal operator corresponding to τ.     

The complexity of locally injective homomorphisms

A homomorphism f:G→H, from a digraph G to a digraph H, is locally injective if the restriction of f to N⁻(v) is an injective mapping, for each v∈V(G). The problem of deciding whether such an f exists is known as the injective H-colouring problem (INJ-HOM_H). In this paper, we classify the problem INJ-HOM_H as being either a problem in P or a problem that is NP-complete. This is done in the case where H is a reflexive digraph (i.e. H has a loop at every vertex) and in the case where H is an irreflexive tournament. A full classification in the irreflexive case seems hard, and we provide some evidence as to why this may be the case.     

Bounds for the number of meeting edges in graph partitioning

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w ₁?Δ₁)/2+2w ₂/3, where wi is the total weight of edges of size i and Δ₁ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w ₀?1)/6+(w ₁?Δ₁)/3+2w ₂/3, where w ₀ is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K ₂ and K _1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott.