An efficient algorithm for a generalized joint replenishment problem

In most multi-item inventory systems, the ordering costs consist of a major cost and a minor cost for each item included. Applying for every individual item a cyclic inventory policy, where the cycle length is a multiple of some basic cycle time, reduces the major ordering costs. An efficient algorithm to determine the optimal policy of this type is discussed in this paper. It is shown that this algorithm can be used for deterministic multi-item inventory problems, with general cost rate functions and possibly service level constraints, of which the well-known joint replenishment problem is a special case. Some useful results in determining the optimal control parameters are derived, and worked out for piecewise linear cost rate functions. Numerical results for this case show that the algorithm significantly outperforms other solution methods, both in the quality of the solution and in the running time.     

Stability of a characterization of the von Mises distribution

Translated from Problemy Ustoichivpsti Stokhasticheskikh Modelei, Trudy Seminara, pp. 73–84, 1986.     

An algorithm for simulation of flows of a generalized Newtonian fluid

This paper addresses a three-parameter iterative method for numeric calculation of generalized Newtonian fluid flows. The method is a generalization of the well-known Arrow-Hurwitz algorithm. The proof of the local convergence of this method is the result of the paper.     

An efficient algorithm for solving generalized pantograph equations with linear functional argument

A numerical method for solving the generalized (retarded or advanced) pantograph equation under initial value conditions is presented. To display the validity and applicability of the numerical method four illustrative examples are presented. The results reveal that this method is very effective and highly promising when compared with other numerical methods, such as Adomian decomposition method, spline methods and Taylor method.     

Expansions for von Mises functionals

Summary Berry-Esseen results and expansions are derived for the distribution function of von Mises functionals of order r under moment conditions and conditions on the smoothness of the limit distribution.The results apply to goodness-of-fit statistics — as well as to the central limit theorem in L ^2p,p2, the rate of convergence being O(n ^–1) for centered balls, provided a fourth moment exists.Research sponsored in part under Office of Naval Research. Contract Number N00014-80-C-0163.     

An efficient generalized least squares algorithm for periodic trended regression with autoregressive errors

Time series data with periodic trends like daily temperatures or sales of seasonal products can be seen in periods fluctuating between highs and lows throughout the year. Generalized least squares estimators are often computed for such time series data as these estimators have minimum variance among all linear unbiased estimators. However, the generalized least squares solution can require extremely demanding computation when the data is large. This paper studies an efficient algorithm for generalized least squares estimation in periodic trended regression with autoregressive errors. We develop an algorithm that can substantially simplify generalized least squares computation by manipulating large sets of data into smaller sets. This is accomplished by coining a structured matrix for dimension reduction. Simulations show that the new computation methods using our algorithm can drastically reduce computing time. Our algorithm can be easily adapted to big data that show periodic trends often pertinent to economics, environmental studies, and engineering practices.     

Inferences based on a bivariate distribution with von Mises marginals

There is very little literature concerning modeling the correlation between paired angular observations. We propose a bivariate model with von Mises marginal distributions. An algorithm for generating bivariate angles from this von Mises distribution is given. Maximum likelihood estimation is then addressed. We also develop a likelihood ratio test for independence in paired circular data. Application of the procedures to paired wind directions is illustrated. Employing simulation, using the proposed model, we compare the power of the likelihood ratio test with six existing tests of independence.     

An efficient multigrid-FEM method for the simulation of solid–liquid two phase flows

An efficient multigrid-FEM method for the detailed simulation of solid–liquid two phase flows with large number of moving particles is presented. An explicit fictitious boundary method based on a FEM background grid which covers the whole computational domain and can be chosen independently from the particles of arbitrary shape, size and number is used to deal with the interactions between the fluid and the particles. Since the presented method treats the fluid part, the calculation of forces and the movement of particles in a subsequent manner, it is potentially powerful to efficiently simulate real particulate flows with huge number of particles. The presented method is first validated using a series of simple test cases, and then as an illustration, simulations of three big disks plunging into 2000 small particles, and of sedimentation of 10,000 particles in a cavity are presented.     

An efficient algorithm for the three-guard problem

Given a simple polygon P with two vertices u and v, the three-guard problem asks whether three guards can move from u to v such that the first and third guards are separately on two boundary chains of P from u to v and the second guard is always kept to be visible from two other guards inside P. It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from u to v and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in O(nlogn) time, and if so generate a walk in O(nlogn+m) time, where n denotes the number of vertices of P and the size of the optimal walk. This improves upon the previous time bounds O(n²) and O(n²logn), respectively. Moreover, our results can be used to solve other more sophisticated geometric problems.     

An algorithm for generalized fractional programs

An algorithm is suggested that finds the constrained minimum of the maximum of finitely many ratios. The method involves a sequence of linear (convex) subproblems if the ratios are linear (convex-concave). Convergence results as well as rate of convergence results are derived. Special consideration is given to the case of (a) compact feasible regions and (b) linear ratios.The research of S. Schaible was supported by Grant Nos. A4534 and A5408 from NSERC. The authors thank two anonymous referees for their helpful remarks.     

An algorithm for generalized rational interpolation

A recursive algorithm for the construction of the generalized form of the interpolating rational function is derived. This generalization of the Neville-Aitken algorithm constructs a table of all possible rational interpolants in implicit form. The algorithm may be simply modified so that it does not break down when a singularity occasionally appears. The coefficients of the interpolant and the evaluation of the interpolant at an arbitrary point may be easily calculated.     

Invariance principles for von Mises and U-statistics

Summary The almost sure approximation of von Mises-statistics and U-statistics by appropriate stochastic integrals with respect to Kiefer processes is obtained. In general these integrals are non-Gaussian processes. As applications we get almost sure versions for the estimator of the variance and for the ²-test of goodness of fit.This work was done while the last author was a visiting professor at the Institut für Mathematische Stochastik at the University of Göttingen during the Spring of 1982. He thanks the Institut and its members for their hospitality     

Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm

We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.The author acknowledges stimulating discussions with J. Piút concerning the main ideas of the present paper. The author is also indebted to P. Brunovský, J. erný, M. Hamala, . Peko, . Znám, and R. Zajac for useful comments.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An algorithm for the symmetric generalized eigenvalue problem

A new method is presented for the solution of the matrix eigenvalue problem Ax=λBx, where A and B are real symmetric square matrices and B is positive semidefinite. It reduces A and B to diagonal form by congruence transformations that preserve the symmetry of the problem. This method is closely related to the QR algorithm for real symmetric matrices.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

An efficient method for solving non-linear singularly perturbed two points boundary-value problems of fractional order

In this paper, we discuss a numerical solution of a class of non-linear fractional singularly perturbed two points boundary-value problem. The method of solution consists of solving reduced problem and boundary layer correction problem. A series method is used to solve the boundary layer correction problem, and then the series solutions is approximated by the Pade’ approximant of order [m, m]. Some theoretical results are established and proved. Two numerical examples are discussed to illustrate the efficiency of the present scheme.     

Asymptotic expansions for bivariate von Mises functionals

Summary A Berry-Essen result and asymptotic expansions are derived for the distribution of bivariate von Mises functionals under moment and smoothness conditions.The results apply to the Cramér-von Mises ² — statistic as well as to the Central Limit Theorem in Hilbert space, yielding a convergence rate O(n _–1+) for every >0 on centered ellipsoids.Herrn Professor Dr. Leopold Schmetterer zu Ehren seines sechzigsten Geburtstages gewidmet     

An efficient sampling scheme for dynamic generalized models

A multimove sampling scheme for the state parameters of non-Gaussian and nonlinear dynamic models for univariate time series is proposed. This procedure follows the Bayesian framework, within a Gibbs sampling algorithm with steps of the Metropolis–Hastings algorithm. This sampling scheme combines the conjugate updating approach for generalized dynamic linear models, with the backward sampling of the state parameters used in normal dynamic linear models. A quite extensive Monte Carlo study is conducted in order to compare the results obtained using our proposed method, conjugate updating backward sampling (CUBS), with those obtained using some algorithms previously proposed in the Bayesian literature. We compare the performance of CUBS with other sampling schemes using two real datasets. Then we apply our algorithm in a stochastic volatility model. CUBS significantly reduces the computing time needed to attain convergence of the chains, and is relatively simple to implement.