The relation of time indexed formulations of single machine scheduling problems to the node packing problem

 The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known results on the facial structure of the scheduling problem. Previous work on the facial structure has focused on describing the convex hull of the set of feasible partial schedules, schedules in which not all jobs have to be started. The equivalence between the characteristic vectors of this set and those of the set of feasible node packings in a graph whose structure is determined by the parameters of the scheduling problem is established. The main contribution of this paper is to show that the facet inducing inequalities for the convex hull of the set of feasible partial schedules that have integral coefficients and right hand side 1 or 2 are the maximal clique inequalities and the maximally and sequentially lifted 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively. Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002 Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities}     

On the interior regularity of weak solutions to the non-stationary Stokes system

In this paper, we prove that any weak solution to the non-stationary Stokes system in 3D with right hand side -div f satisfying (1.4) below, belongs to C( ]0, T[; C ^α (Ω)). The proof is based on Campanato-type inequalities and the existence of a local pressure introduced in Wolf [13]. Proc. Conference “Variational analysis and PDE’s”. Intern. Centre “E. Majorana”, Erice, July 5–14, 2006.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

Basic properties of solution of the non-steady Navier–Stokes equations with mixed boundary conditions in a bounded domain

In this paper we deal with the system of the non-steady Navier–Stokes equations with mixed boundary conditions. We study the existence and uniqueness of a solution of this system. Suppose that the system is solvable with some given data (the initial velocity and the right hand side). We prove that there exists a unique solution of this system for data which are small perturbations of the previous ones.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

An optimum multivariate stratified double sampling design in presence of non-response

In stratified sampling when strata weights are unknown double sampling technique may be used to estimate them. At first a large simple random sample from the population without considering the stratification is drawn and sampled units belonging to each stratum are recorded to estimate the unknown strata weights. A stratified random sample is then obtained comprising of simple random subsamples out of the previously selected units of the strata. If the problem of non-response is there, then these subsamples may be divided into classes of respondents and non-respondents. A second subsample is then drawn out of non-respondents and an attempt is made to obtain the information. This procedure is called Double Sampling for Stratification (DSS). Okafor (Aligarh J Statist 14:13–23, 1994) derived DSS estimators based on the subsampling of non-respondents. Najmussehar and Bari (Aligarh J Statist 22:27–41, 2002) discussed an optimum double sampling design by formulating the problem as a mathematical programming problem and used the dynamic programming technique to solve it. In the present paper a multivariate stratified population is considered with unknown strata weights and an optimum sampling design is proposed in the presence of non-response to estimate the unknown population means using DSS strategy. The problem turns out to be a multiobjective integer nonlinear programming problem. A solution procedure is developed using Goal Programming technique. A numerical example is presented to illustrate the computational details.     

CLT for linear random fields with martingale increments

In [V. Paulauskas, On Beveridge–Nelson decomposition and limit theorems for linear random fields, J. Multivariate Anal., 101:621–639, 2010], limit theorems for linear random fields generated by independent identically distributed innovations were proved. In this paper, which can be regarded as a continuation of the above-mentioned paper, CLT for sums of linear random field are proved in the case where innovations form martingale differences on the plane (that can be defined in several ways). In both papers, the so-called Beveridge–Nelson decomposition is used.     

Improved seed methods for symmetric positive definite linear equations with multiple right‐hand sides

We consider symmetric positive definite systems of linear equations with multiple right‐hand sides. The seed conjugate gradient (CG) method solves one right‐hand side with the CG method and simultaneously projects over the Krylov subspace thus developed for the other right‐hand sides. Then the next system is solved and used to seed the remaining ones. Rounding error in the CG method limits how much the seeding can improve convergence. We propose three changes to the seed CG method: only the first right‐hand side is used for seeding, this system is solved past convergence, and the roundoff error is controlled with some reorthogonalization. We will show that results are actually better with only one seeding, even in the case of related right‐hand sides. Controlling rounding error gives the potential for rapid convergence for the second and subsequent right‐hand sides. Polynomial preconditioning can help reduce storage needed for reorthogonalization. The new seed methods are applied to examples including matrices from quantum chromodynamics. Copyright © 2013 John Wiley & Sons, Ltd.     

Random integral manifolds of systems of differential equations with unbounded operator in a Banach space

We establish existence conditions for a random integral manifold of a certain class of differential systems with unbounded sectorial operator and random right-hand side in a Banach space. Translated from Ukrainskii Matematicheskii Zhumal, Vol. 50, No. 12, pp. 1609–1614, December, 1998.     

A non-uniform Berry–Esseen bound via Stein's method

This paper is part of our efforts to develop Stein's method beyond uniform bounds in normal approximation. Our main result is a proof for a non-uniform Berry–Esseen bound for independent and not necessarily identically distributed random variables without assuming the existence of third moments. It is proved by combining truncation with Stein's method and by taking the concentration inequality approach, improved and adapted for non-uniform bounds. To illustrate the technique, we give a proof for a uniform Berry–Esseen bound without assuming the existence of third moments. Received: 2 March 2000 / Revised version: 20 July 2000 / Published online: 26 April 2001     

Maximum and minimum solutions for nonlinear parabolic problems with discontinuities

In this paper we examine nonlinear parabolic problems with a discontinuous right hand side. Assuming the existence of an upper solution φ and a lower solution ψ such that ψ ≤ φ, we establish the existence of a maximum and a minimum solution in the order interval [ψ, φ]. Our approach does not consider the multivalued interpretation of the problem, but a weak one side “Lipschitz” condition on the discontinuous term. By employing a fixed point theorem for nondecreasing maps, we prove the existence of extremal solutions in [ψ, φ for the original single valued version of the problem.     

Asymptotic normality of the Parzen–Rosenblatt density estimator for strongly mixing random fields

We prove the asymptotic normality of the kernel density estimator (introduced by Rosenblatt, Proc Natl Acad Sci USA 42:43–47, 1956 and Parzen, Ann Math Stat 33:1965–1976, 1962) in the context of stationary strongly mixing random fields. Our approach is based on the Lindeberg’s method rather than on Bernstein’s small-block-large-block technique and coupling arguments widely used in previous works on nonparametric estimation for spatial processes. Our method allows us to consider only minimal conditions on the bandwidth parameter and provides a simple criterion on the strong mixing coefficients which do not depend on the bandwidth.     

α-Transience and α-Recurrence of Right Processes

In this article, we mainly discuss some potential theory in the framework of right Markov processes. We introduce the concept of α-excessive function, α-recurrence and α-transience for right processes with α ≤ 0, and give a thorough investigation.     

Universal bounds on the selfaveraging of random diffraction measures

 We consider diffraction at random point scatterers on general discrete point sets in ℝ^ν, restricted to a finite volume. We allow for random amplitudes and random dislocations of the scatterers. We investigate the speed of convergence of the random scattering measures applied to an observable towards its mean, when the finite volume tends to infinity. We give an explicit universal large deviation upper bound that is exponential in the number of scatterers. The rate is given in terms of a universal function that depends on the point set only through the minimal distance between points, and on the observable only through a suitable Sobolev-norm. Our proof uses a cluster expansion and also provides a central limit theorem. Received: 10 October 2001 / Revised version: 26 January 2003 / Published online: 15 April 2003 Work supported by the DFG Mathematics Subject Classification (2000): 78A45, 82B44, 60F10, 82B20 Key words or phrases: Diffraction theory – Random scatterers – Random point sets – Quasicrystals – Large deviations – Cluster expansions     

Simulation of Brown–Resnick processes

Brown–Resnick processes form a flexible class of stationary max-stable processes based on Gaussian random fields. With regard to applications, fast and accurate simulation of these processes is an important issue. In fact, Brown–Resnick processes that are generated by a dissipative flow do not allow for good finite approximations using the definition of the processes. On large intervals we get either huge approximation errors or very long operating times. Looking for solutions of this problem, we give different representations of the Brown–Resnick processes—including random shifting and a mixed moving maxima representation—and derive various kinds of finite approximations that can be used for simulation purposes. Furthermore, error bounds are calculated in the case of the original process by Brown and Resnick (J Appl Probab 14(4):732–739, 1977). For a one-parametric class of Brown–Resnick processes based on the fractional Brownian motion we perform a simulation study and compare the results of the different methods concerning their approximation quality. The presented simulation techniques turn out to provide remarkable improvements.     

Inequalities of Maximum of Partial Sums and Weak Convergence for a Class of Weak Dependent Random Variables

In this paper, we establish a Rosenthal-type inequality of the maximum of partial sums for ρ^- -mixing random fields. As its applications we get the Hájeck -Rènyi inequality and weak convergence of sums of ρ^- -mixing sequence. These results extend related results for NA sequence and p^＊ -mixing random fields,     

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

The Cauchy Problem for the Generalized Korteweg-de Vries-Benjamin-Ono Equation with Low Regularity Data

The Cauchy problem of the generalized Korteweg-de Vries-Benjamin-Ono equation is considered, and low regularity and limit behavior of the solutions are obtained. For k = 1, local well- posedness is obtained for data in H^s（R）（s 〉 -3/4）. For k = 2, local result for data in H^S（R）（s 〉1/4） is obtained. For k = 3, local result for data in H^S（R）（s 〉 -1/6） is obtained. Moreover, the solutions of generalized Korteweg-de Vries-Benjamin-Ono equation converge to the solutions of KdV equation if the term of Benjamin-Ono equation tends to zero.     

Some insights into the solution algorithms for SLP problems

We consider classes of stochastic linear programming problems which can be efficiently solved by deterministic algorithms. For two–stage recourse problems we identify two such classes. The first one consists of problems where the number of stochastically independent random variables is relatively low; the second class is the class of simple recourse problems. The proposed deterministic algorithm is successive discrete approximation. We also illustrate the impact of required accuracy on the efficiency of this algorithm. For jointly chance constrained problems with a random right–hand–side and multivariate normal distribution we demonstrate the increase in efficiency when lower accuracy is required, for a central cutting plane method. We support our argumentation and findings with computational results.     

On a class of stochastic models with two-sided jumps

In this paper a stochastic process involving two-sided jumps and a continuous downward drift is studied. In the context of ruin theory, the model can be interpreted as the surplus process of a business enterprise which is subject to constant expense rate over time along with random gains and losses. On the other hand, such a stochastic process can also be viewed as a queueing system with instantaneous work removals (or negative customers). The key quantity of our interest pertaining to the above model is (a variant of) the Gerber–Shiu expected discounted penalty function (Gerber and Shiu in N. Am. Actuar. J. 2(1):48–72, 1998) from ruin theory context. With the distributions of the jump sizes and their inter-arrival times left arbitrary, the general structure of the Gerber–Shiu function is studied via an underlying ladder height structure and the use of defective renewal equations. The components involved in the defective renewal equations are explicitly identified when the upward jumps follow a combination of exponentials. Applications of the Gerber–Shiu function are illustrated in finding (i) the Laplace transforms of the time of ruin, the time of recovery and the duration of first negative surplus in the ruin context; (ii) the joint Laplace transform of the busy period and the subsequent idle period in the queueing context; and (iii) the expected total discounted reward for a continuous payment stream payable during idle periods in a queue.