Stochastic Recursive Equations with Applications to Queues with Dependent Vacations

We focus on a special class of nonlinear multidimensional stochastic recursive equations in which the coefficients are stationary ergodic (not necessarily independent). Under appropriate conditions, an explicit ergodic stationary solution for these equations is obtained and the convergence to this stationary regime is established. We use these results to analyze several queueing models with vacations. We obtain explicit solutions for several performance measures for the case of general non-independent vacation processes. We finally extend some of these results to polling systems with general vacations.     

Equations with Random Gaussian Operators with Unbounded Mean Value

We consider an equation in a Hilbert space with a random operator represented as a sum of a deterministic, closed, densely defined operator and a Gaussian strong random operator. We represent a solution of an equation with random right-hand side in terms of stochastic derivatives of solutions of an equation with deterministic right-hand side. We consider applications of this representation to the anticipating Cauchy problem for a stochastic partial differential equation.     

Scheduling with partial rejection

We study a single machine scheduling problem with partial rejection. Each job is with an integer processing time. Partial rejection occurs when a job is only partly processed with penalty for the rejected part. We focus on integer size rejection. The objective is to minimize the total weighted completion time of processed jobs plus the total rejection cost. We develop a polynomial time optimal algorithm to solve the problem. We also present an easy-to-implement pseudopolynomial time optimal algorithm.     

Characterization of integral operators with semi-separable kernels with symmetries

We characterize integral operators with semi-separable kernels in a certain class that have different symmetries. We treat the selfadjoint case, the positive case, the J-unitary case, the positive real case, the dissipative case and the contractive case.     

Differential evolution with preferential crossover

We study the mutation operation of the differential evolution algorithm. In particular, we study the effect of the scaling parameter of the differential vector in mutation. We derive the probability density function of points generated by mutation and thereby identify some drawbacks of the scaling parameter. We also visualize the drawbacks using simulation. We then propose a crossover rule, called the preferential crossover rule, to reduce the drawbacks. The preferential crossover rule uses points from an auxiliary population set. We also introduce a variable scaling parameter in mutation. Motivations for these changes are provided. A numerical study is carried out using 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the proposed modification reduces the number of function evaluations and cpu time considerably.     

Mols with holes

We consider sets of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning. We give several constructions for sets of MOLS with holes.     

Multi-Particle Processes with Reinforcements

We consider a multi-particle generalization of linear edge-reinforced random walk (ERRW). We observe that in absence of exchangeability, new techniques are needed in order to study the multi-particle model. We describe an unusual coupling construction associated with the two-point edge-reinforced process on ℤ and prove a form of recurrence: the two particles meet infinitely often a.s. This research was supported in part by NSF VIGRE Grant DMS 9983726 at UCLA.     

Estimation with Missing Data

This paper reviews estimation problems with missing, or hidden data. We formulate this problem in the context of Markov models and consider two interrelated issues, namely, the estimation of a state given measured data and model parameters, and the estimation of model parameters given the measured data alone. We also consider situations where the measured data is, itself, incomplete in some sense. We deal with various combinations of discrete and continuous states and observations.     

Besov Spaces with General Weights

We introduce Besov spaces with general smoothness. These spaces unify and generalize the classical Besov spaces. We establish the $\varphi $-transform characterization of these spaces in the sense of Frazier and Jawerth and we prove their Sobolev embeddings. We establish the smooth atomic, molecular and wavelet decomposition of these function spaces. A characterization of these function spaces in terms of the difference relations is given.     

Codes with a Disparity Property

Kth order zero disparity codes have been considered in several recent papers. In the first part of this paper we remove the zero disparity condition and consider the larger class of codes, Kth order disparity D codes. We establish properties of disparity D codes showing that they have many of the properties of zero disparity codes. We give existence criteria for them, and discuss how new codewords may be formed from ones already known. We then discuss Kth order disparity D codes that have the same number of codewords. We discuss the minimum distance properties of these new codes and present a decoding algorithm for them. In the second part of the paper we look at how the minimum distance of disparity D codes can be improved. We consider subsets of a very specialised subclass, namely first order zero disparity codes over alphabet Aq of size q. These particular subsets have q codewords of length n and minimum Hamming distance n. We show that such a subset exists when q is even and nis a multiple of 4, and also when q is odd and n is even. These subsets have the best error correction capabilities of any subset of q first order zero disparity codewords.     

Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand

We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach.     

Electrodynamics with charged strings

We show that in a four-dimensional space–time a complex scalar field can be associated with a one-dimensionally extended object, called a charged string. The string is said to be charged because the complex scalar field describing it interacts with an electromagnetic field. A charged string is characterized by an extension of the symmetry group of the charge space to a group of stretch rotations. We propose relativistically invariant and gauge-invariant equations describing the interaction of a complex scalar field with an electromagnetic field, and each solution of them corresponds to a charged string. We achieve this by introducing the notion of a charged string index, which, as verified, takes only integer values. We establish equations from which it follows that charged strings fit naturally into the framework of the Maxwell–Dirac electrodynamics.     

Clinic scheduling models with overbooking for patients with heterogeneous no-show probabilities

Clinical overbooking is intended to reduce the negative impact of patient no-shows on clinic operations and performance. In this paper, we study the clinical scheduling problem with overbooking for heterogeneous patients, i.e. patients who have different no-show probabilities. We consider the objective of maximizing expected profit, which includes revenue from patients and costs associated with patient waiting times and physician overtime. We show that the objective function with homogeneous patients, i.e. patients with the same no-show probability, is multimodular. We also show that this property does not hold when patients are heterogeneous. We identify properties of an optimal schedule with heterogeneous patients and propose a local search algorithm to find local optimal schedules. Then, we extend our results to sequential scheduling and propose two sequential scheduling procedures. Finally, we perform a set of numerical experiments and provide managerial insights for health care practitioners.     

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper.     

Reflected BSDEs with regulated trajectories

We consider reflected backward stochastic different equations with optional barrier and so-called regulated trajectories, i.e. trajectories with left and right finite limits. We prove existence and uniqueness results. We also show that the solution corresponds to the value of an optimal stopping problem and may be approximated by a modified penalization method.     

Hermite interpolation with symmetric polynomials

We study the Hermite interpolation problem on the spaces of symmetric bivariate polynomials. We show that the multipoint Berzolari-Radon sets solve the problem. We also give a Newton formula for the interpolation polynomial and use it to prove a continuity property of the interpolation polynomial with respect to the interpolation points.     

Tree wavelet approximations with applications

We construct a tree wavelet approximation by using a constructive greedy scheme (CGS). We define a function class which contains the functions whose piecewise polynomial approximations generated by the CGS have a prescribed global convergence rate and establish embedding properties of this class. We provide sufficient conditions on a tree index set and on bi-orthogonal wavelet bases which ensure optimal order of convergence for the wavelet approximations encoded on the tree index set using the bi-orthogonal wavelet bases. We then show that if we use the tree index set associated with the partition generated by the CGS to encode a wavelet approximation, it gives optimal order of convergence.     

A problem with formal initial conditions for differential equations with constant pseudodifferential coefficients

We establish conditions for the unique existence of a solution of a problem with formal initial conditions. We investigate the problem of its solvability in the case where a solution is not unique.     

Complex Cauchy Problems with Intersecting Singularities

We consider linear Cauchy problems of order two in a complex domain. We assume that the initial values have singularities along a family of hypersurfaces, which cross pairwise transversally along a single intersection. We study the propagation of the singularities of the solution. We show that the solution may have anomalous singularities, and study the monodromy of the solution.     

On acyclicity of games with cycles

We study restricted improvement cycles (ri-cycles) in finite positional n-person games with perfect information modeled by directed graphs (di-graphs) that may contain directed cycles (di-cycles). We assume that all these di-cycles form one outcome c, for example, a draw. We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n=2 and for acyclic di-graphs. We provide several examples that outline the limits of these criteria and show that, essentially, there are no other ri-acyclic cases.We also discuss connections between ri-acyclicity and some open problems related to Nash-solvability.