Search

In this note the authors call for a change of the optimality criteria given by Theorem 3 in section 5 of the paper of W. Szwarc “On Some Sequencing Problems” in NRLQ Vol. 15, No. 2 [2]. Further, two cases of the three machine problem, namely, (i) ≦ and (ii) ≦ are considered, and procedures for obtaining optimal sequences in these cases are given. In these cases the three-machine problem is solved by solving n (the number of jobs) two-machine problems.

n/a

Summary A table and a nomogram are given to find the growth rate of a regression line drawn on so-called semi-logarithmic graph paper. The growth rate is determined by: a) the slope of the regression line, b) the length ratio between the logarithmic and the metric unit, in other words, the number of years on the time axis (if a year is the time unit) corresponding in length to one cycle on the logarithmic axis (say, 1 to 10, or 100 to 1000). With an example, the use of the table and nomogram is explained.

The main new difficulties encountered are the possible existence of inseparable elements in the finite extension ft/P, and also the occurrence of constant field extensions. The former phenomenon is overcome in §1 by the device of replacing P by a suitable purely inseparable extension K s fi for which " descent by norms " to P behaves in a reasonable manner. We then attempt to imitate where possible the processes of [1] applied to Q.JK. The presence of constant field extensions inevitably complicates the analysis, since the " obvious " analogue of Cebotarev's density theorem is unexpectedly false in this case. We append to this paper a section on the appropriate Cebotarev theorem which, we hope, will fill the gap in the literature of this intriguing topic. Section 2 of this paper corresponds broadly to §1 of [1], and in it we prove THEOREM 1IA. Let G¥(q s ) be the constant field ofd, a finite extension of P. Then the number of integral ideals ofk[X] which have degree d, are prime to a given ideal n, and are norms of fractional ideals of Cl is zero unless f divides d, in which case the number is asymptotically

This paper is designed to treat (a) the problem of the determination of the absolute minimum cost, with the associated assignments, when there is no limit, N, on the number of parcels available for shipment in a modified Hitchcock problem. This is accomplished with the use of a transformed cost matrix. C*, to which the so-called transportation paradox does not apply. The general Hitchcock solution using C* gives the cost T*, which is the absolute minimum cost of the original problem, as well as sets of assignments which are readily transformed to give the general assignments of the original problem. The sum of these latter assignments gives the value of Nu, the unbounded N for minimum cost. In addition, this paper is designed to show (b) how the method of reduced matrices may be used, (c) how a particular Hitchcock solution can be used to determine a general solution so that one solution using C* can provide the general answer, (d) how the results may be modified to apply to problems with fixed N, and hence (e) to determine the function of the decreasing T as N approaches Nu, and finally (f) to provide a treatment when the supplies at origin i and/or the demands at destination j, are bounded.

The paper makes some remarks on the paper of Hakimi and Frank and shows a simplified way of applying the concept of alternating forest. An algorithm for finding a maximum internally stable set of an undirected graph is constructed and some examples are given.

In this paper, the existence of a saddle point for two-person zero-sum infinite games of a special type is proved. The games have continuous bilinear payoff functions and strategy sets which are convex, noncompact subsets of an infinite-dimensional vector space. The closures of the strategy sets are, however, compact. The payoff functions satisfy conditions which allow the use of dominance arguments to show that points in the closure of a strategy set are dominated by or are strategically equivalent to points in the strategy set itself. Combining the dominance arguments with a well-known existence theorem produces the main result of the paper. The class of games treated is an extension of a class studied by J. D. Matheson, who obtained explicit solutions for the saddle points by using necessary conditions.

SUMMARY This paper contains a study of the departure process from M/G/1 queues with a waiting space of size N> 0. The property of the departure process which receives the most attention is the covariance of pairs of departure intervals, although a more thorough investigation of the probabilistic structure is undertaken for the case N= 1. A main result of the paper is that in the M/G/1 queue with N = 1, departure intervals separated by one or more intervals are independent. When G is the deterministic server, the departure stream is a renewal process. The paper concludes with an expression for the covariance of any pair of intervals in the departure process for any value of N, and numerical values for correlations in the case of a deterministic server with N= 2.

In two earlier papers, we proposed algorithms for finding an optimal sequence of processing m items on q machines, by finding a minimaximal path in a disjunctive network. In a third paper, this latter model was generalized (from 2-state to 3-state disjunctive graphs) so as to accommodate project scheduling with resource constraints. In this paper, we discuss another algorithm for the (2-state) disjunctive network problem, closely related to those mentioned above. To make the paper self-contained, section 2 briefly describes the problem. Section 3 introduces a class of constraints which forms the basis of the algorithm discussed in section 4. The constraints have only 1, −1, or 0 as coefficients on the left-hand side, integers on the right-hand side. The whole procedure of generating these constraints and finding a feasible solution whenever a new constraint is added, can be interpreted (section 5) as a process of generating a graph with degree-constraints on its nodes, and then finding a subgraph satisfying the degree-constraints. The nodes of the graph are generated by solving a critical-path-problem, the feasible subgraphs are found by implicit enumeration.

Ch. L. Lawson hat kurzlich eine Theorie der rationalen Segmentapproximation aufgestellt. In der vorliegenden Note wird untersucht, wie die besten Trennpunkte im Falle der Polynomapproximation berechnet werden konnen. Hierbei wird ein Monotonieprinzip wesentlich benutzt, uber das in der voranstehenden Arbeit berichtet wurde. Recently Ch. L. Lawson developed a theory of rational segmential approximation. The present paper deals with the problem of computing the best separating points in the case of polynomials. The main tool is a principle of monotony which has been discussed in the preceeding paper.

for a certain c. In fact I shall prove that if n is highly composite, then the next highly composite number is less than n+n(log y&)-C ; and the result just stated follows immediately from this. At, present I cannot, decide whether the number of highly composite numbers not exceeding z is greater than (logx)” for every k. The principal tool in the proof will be Ingham’s improvement,$ on Hoheisel’s theorem. This asserts that if x is sufficiently large, then the number of primes in the int,erval (x, x+&) is asymptot.ic to cxg(logz)-1. First we state three lemmas, which will be proved at the end of the paper. They are contained subst’antially in the paper of Ramanujan, but we prove Ohem here for completeness. Let n = 22 3~ . . . p+ be a sufficiently large highly composite number. Plainly

SUMMARY We say that a single server queue is in "heavy traffic" when the traffic intensity p is less than, but very near, unity. Then the equilibrium waiting time w will be large, and it is proved that, under certain conditions, the It is therefore of some interest to ask if there are any results which hold under somewhat weaker conditions. It is not to be expected that these will be results valid in general, but rather that they will hold in some limiting case. The limiting case to be considered here is that usually known as "heavy traffic". A common way of formulating queueing problems with a single server is in terms of a traffic intensity p defined as the average number of customers arriving during a service period. For p > 1 the queue will be stable, while for p > 1 its length will increase indefinitely as time goes on. In particular, when p < 1 an equilibrium waiting-time distribution will exist, and as p approaches 1 from below, this waiting time will become long. This situation, when p is less than, but near, unity, we describe as "heavy traffic". The main conclusion of the present paper may roughly be stated as follows: If w is the equilibrium waiting time, then the distribution of (1- p)w is asymptotically negative exponential as p tends to 1. The parameter of this exponential distribution is given in terms of the means and variances of the input and service processes. In the particular case of the queue GI/G/l the result has been proved by the author (1961). We shall first indicate heuristically why this result is to be expected, and what conditions it is necessary to impose. A rigorous proof is then given for a wide class of queues, and this is shown to include a number of cases of interest. The correspond- ing analysis for the queue length and the busy period is also briefly discussed. All the work in this paper may be re-interpreted in the usual way in terms of random walks or semi-infinite dams.

It was proved by Roth in a recent paper that if α is any real algebraic number, and if K > 2, then the inequalityhas only a finite number of solutions in relatively prime integers p, q (q > 0) The object of the present paper is to prove that the lower bound for κ can be reduced if conditions are imposed on p and q. The result obtained is as follows.

M. D. ATKINSONIn a series of papers [3, 4 and 5] on insoluble (transitive) permutation groupsof degree p = 2q +1, where p and q are primes, N. Ito has shown that, apart from asmall number of exceptions, such a group must be at least quadruply transitive.One of the results which he uses is that an insoluble 2q grou +1 p of degree p =which is not doubly primitive must be isomorphi (3, 2)c wit to PSh p =L 7. Thisresult is due to H. Wielandt, and ltd gives a proof in [3]. It is quite easy to extendthis proof to give the following result: a doubly transitive group of degree 2q + l,where q is prime, which is not doubly primitive, is either sharply doubly transitiveor a group of automorphisms of a bloc A = 1 ank desigd k = 3n wit. Ouh rnotation for the parameters of a block design, v, b, X, k, i r,s standard; see [9].In this paper we shall prove two results about doubly transitive but not doublyprimitive groups which resemble the two results mentioned above.

An optimization problem which frequently arises in applications of mathematical programming is the following: Where fi are convex functions. In this paper, the function F is studied and shown to satisfy F(A, B) = M (A) + N(B), where M and N are increasing and decreasing convex functions, respectively. Also, the functional equation F (A, C) = F(A, B) + F(B, C) − F(B, B) is established. These results generalize to the continuous case F(A, B)=min ∫ f(t, x(t))dt, with x(t) increasing and A ≤ x (0) ≤ x (T) ≤ B. The results obtained in this paper are useful for reducing an optimization problem with many variables to one with fewer variables.

The object of this paper is to give proofs of the following theorems: Every sufficiently large number is representable as the sum of 14 fourth powers, unless it is congruent to 15 or 16 (mod 16). Every sufficiently large number is representable as the sum of 15 fourth powers, unless it is of the form 16hk, where k has one of a finite number of values. Every sufficiently large number is representable as the sum of 16 fourth powers. The second and third of these theorems are immediate consequences of the first. It is well known that the third theorem is the best possible result of its kind, since 16h X 31 is not the sum of less than 16 fourth powers. These results are a considerable improvement on the theorem (proved simultaneously by Estermann and by Heilbronn and myself) that every large number is the sum of 17 fourth powers. The improvement results from the use of a new method, of which I have given accounts elsewhere,' for constructing different numbers which are the sums of s positive integral kth powers. The reader who is familiar with Waring's problem will see from the proof of Lemma 1 exactly what the new idea is, and will probably be content to take the rest of the paper for granted. But for the sake of other readers, the whole proof has been presented in fairly complete detail. The only external sources referred to are: (1) Landau, Vorlesungen ziber Zahlentheorie (Leipzig, 1927), volume 1; (2) Davenport and Heilbronn, "On an exponential sum," Proc. London Math. Soc., 41 (1936), 449-453.

Summary The plotting of observations on probability paper The mathematical foundation of probability paper for a variate with a cumulative distribution function F (αx+β) is explained as well as its purpose. To plot the observations it is necessary to use an estimate cf F (xi, xi being the 1 th order statistic in the sample. Several methods are described and compared, and a new one is developed, having the property that with a very good approximation the medians of xi are situated on a straight line. The derivations are given separately in an appendix.

In an earlier paper [1] we put forth a framework that helps to tie together a number of approaches for solving integer programming problems. We outlined there how Balas' Additive Algorithm can be explained and generalized in terms of the framework. In the present paper we review Balas' algorithm, and our earlier framework, and present an algorithm generalizing Balas' scheme. In addition, some examples are presented and future research to be done is discussed.

The paper deals with the adjustment of examiners’ marks for a single test when the scripts are marked by several independent examiners, each of whom is assigned a different but statistically equivalent set of scripts.

This paper selectively reviews some of the recent developments in sequencing objects along a continuum that rely upon a symmetric proximity measure defined between the objects to be seriated. Most of the discussion is from a graph-theoretical point of view and emphasizes the notion of a maximal spanning tree and related ‘crude’ seriation strategies that require only the ordinal information from the basic proximity values. In addition, correspondences with several hierarchical clustering techniques are presented as well as an extension to the newer circular-arc models developed in mathematics. A number of substantive examples are given incorporating data sets available in the psychological literature that have been analysed previously with alternative methods.

This paper presents a simple algorithm for finding the number of restricted k-partitions of a natural number n. The unrestricted k-partitions of n are expressed as the sum of these restricted k-partitions, called inadmissible, and the admissible k-partitions. The simplicity of the algorithm is striking, though all the implications are unclear.

In this paper is proved a formula for the number of neighbourly d-polytopes with d + 3 vertices, when d is odd.

The discrete (Legendre) orthogonal polynomials, (DLOP's) are useful for approximation purposes. This set of mth degree polynomials {Pm(K, N)} are orthogonal with unity weight over a uniform discrete interval and are completely determined by the normalization Pm(O, N) = 1. The authors are employing these polynomials as assumed modes in engineering applications of weighted residual methods. Since extensive material on these discrete orthogonal polynomials, and their properties, is not readily available, this paper is designed to unify and summarize the presently available information on the DLOP's and related polynomials. In so doing, many new properties have been derived. These properties, along with sketches of their derivation, are included. Also presented are a representation of the DLOP's as a product of vectors and matrices, and an efficient computational scheme for generating these polynomials.

The object of this paper is to describe a new algorithm for the semi-automatic triangulation of arbitrary, multiply connected planar domains. The strategy is based upon a modification of a finite element mesh genration algorithm recently developed. 1 The scheme is designed for maximum flexibility and is capable of generating meshes of triangular elements for the decomposition of virtually any multiply connected planar domain. Moreover, the desired density of elements in various regions of the problem domain is specified by the user, thus allowing him to obtain a mesh decomposition appropriate to the physical loading and/or boundary conditions of the particular problem at hand. Several examples are presented to illustrate the applicability of the algorithm. An extension of the algorithm to the triangulation of shell structures is indicated.

The paper discusses mathematical properties of the well-known Bellman-Johnson 3 × n sequencing problem. Optimal rules for some special cases are developed. For the case min Bi ≥ maxAj we find an optimal sequence of the 2 × n problem for machines B and C and move one item to the front of the sequence to minimize (7); when min Bi ≥ max Cj we solve a 2 × n problem for machines A and B and move one item to the end of the optimal sequence so as to minimize (9). There is also given a sufficient optimality condition for a solution obtained by Johnson's approximate method. This explains why this method so often produces an optimal solution.

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.

This paper deals with the problem (raised by J. Browkin) of how many ring generators are needed for the ring of integers of a given algebraic number field. I show that the number of generators needed for the integers of a field of degree n is less than (log n /log2) + 1, and that if 2 splits completely in the field the number of generators needed is in fact the largest integer less than (log n /log2) + 1. These results follow from a computable formula (that depends only on how the small primes factorize in the field) for the number of generators of the ring of integers of a given field. This formula has the single drawback that when it yields “one” two generators may be needed, and I show that there are fields of arbitrarily high degree for which this happens.

Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular-arc graph. In this paper we give a characterization of the circular-arc graph and we describe efficient algorithms for recognizing two subclasses. Also, we describe efficient algorithms for finding a maximum independent set, a minimum covering by cliques and a maximum clique of a circular-arc graph.

In this paper we prove that the point in a triangle T maximizing the probability that it lies within a randomly chosen triangle within T is the center of T. A simple general closed expression for the indicated probability at any point P of T is obtained, though the proof proceeds by a symmetry argument on contributions to derivatives of the probability. It is also shown that the indicated probability is linearly related to the average over points in T of the product of the areas within T on either side of the line determined by P and . This gives the proof for n = 3 of the following conjecture of A. Prekopa: Fix a point P in an n − 1 dimensional simplex S. Take n independent points, uniformly distributed in S, and consider the probability ρ(P) of P being inside the random simplex determined by these n points. Conjecture: ρ(P) is maximal, when P is the center of gravity of S.

This paper gives a formulation of a theory of n-person cooperative games with side payments in terms of a partition function which is defined on the set of all partitions of the set of players. The results for all games with n ≤ 3 are presented. This development generalizes the von Neumann-Morgenstern theory of games in characteristic function form.

In 1956 Cassels proved the following result, which generalized a theorem of Marshall Hall on continued fractions. Let λ 1 …, λ r be any real numbers. Then there exists a real number α such that for all integers u > 0 and for q = 1,…,r , where C = C(r) > 0. Thus all the numbers α+ λ 1 , …, α+ λ r are badly approximable by rational numbers, which is equivalent to saying that the partial quotients in their continued fractions are bounded. In a previous paper I extended Cassels's result to simultaneous approximation. In the simplest case—that of simultaneous approximation to pairs of numbers—I proved that for any real λ 1 , …, λ r and μ 1 , …, μ r there exist α, β such that for all integers u > 0 and for q=1,…, r , where again C = C(r) > 0 . Both the construction of Cassels and my extension of it to more dimensions allow one to introduce an infinity of arbitrary choices, and consequently the set of α for (1) and the set of α, β for (2) may be made to have the cardinal of the continuum.

Let Xt (t = 1, 2, ..., N) denote a series of independent normal random variables, with zero means and non-zero finite variances ft (t = 1, 2, ..., N). Then ft and ft 1 admit finite Fourier expansions. The present paper is a study of the statistics N-1 S Xt cos (2tts/N) and Nt t Xt sin (2'rrts/N) as estimators of the sth Fourier coefficients of ft, and of the distributional properties of suitable ratios of these statistics as (sufficient) test statistics for non-constancy of ft, directed at alternatives where the Fourier expansion of ft 1 has a simple form.

Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum independent set of circle graphs. These algorithms require at most n3 steps, where n is the number of vertices in the graph.

The paper contains the following new results concerning the solvability of the DC equations and the implicit integration formula of a broad class of nonlinear networks. (i) A new method of proof is given. (ii) Conditions are given for checking the unique solvability of the DC equation F(x)+Ax = b in case of monotone (not strictly monotone) and ‘steep’ characteristics and in the case when the characteristics have negative slope. Furthermore existence theorems are given under very weak conditions. (iii) In the case of a broad class of nonlinear networks sufficient conditions are presented for the unique solvability of the implicit integration formula when the characteristics are monotone or have negative slope. Some practical consequences of the theorems are also discussed.

The effects of random degradation on the molecular weight averages for broad Schulz-Zimm and Wesslau type distributions are evaluated by blending two most probable Flory type distributions so that the Mn:Mw:Mz ratios of the blend were equal to that of the distribution models for any particular Mw/Mn ratio. The results indicate a rather extreme sensitivity of broad Wesslau distributions to small degrees of degradation and suggest that this function is not a good description for polyolefins.

When a subject makes a number of discriminations between pairs of reference objects, each time saying which of the pair is closer in value to a test object, there arise two problems: (1) deciding which patterns of responses are internally consistent and (2) scaling the consistent response patterns. This paper generalizes Shapiro's solution for the case of three reference objects. (1) The identification of consistent response patterns requires a certain partial higher-ordered metric scaling of the reference objects; however, if certain incomplete sets of judgements are used, then only an ordinal scaling of the reference objects is demanded. (2) The consistent response patterns can be ordinally scaled, but only a rudimentary partial higher-ordered metric scale can be established.

Let K(x1, x2, , xn) be a graph without loops or multiple edges, the complement of which consists of n disjoint complete graphs of x1, x2, , xn vertices. In this paper a class of mappings of K(x1, , xn) onto the Euclidean plane is described. The minimum number of intersection points of edges for these mappings is determined. This number also involves an upper bound for the so-called crossing number cr(x1, , xn), being the minimum number of intersection points of edges for all mappings of K(x1, , xn) onto the Euclidean plane (see (28)). Equality in (28) is conjectured.

The paper studies combinatorial aspects of the lattice of subspaces of a vector space over a finite field and its use in deriving classical and new q-identities. Set theoretic interpretations of these identities are given in terms of the enumeration of vector spaces and linear transformations. The incidence algebra of a partially ordered set is shown to be a true generalization of the notion of a generating function and Eulerian generating functions are applied to count a variety of vector space objects. Combinatorial interpretations are provided for general q-difference equations. (Author)

S(H: E fG) = h{P(H. E. G), P(E. G), P(H)}-h{P(G. H), P(G), P(H)} and the proof of Theorem 6 is invalidated. A valid proof can, however, be constructed without undue difficulty and the details will be supplied on request. Professor Aczel and I believe that, by using methods of Aczel (1966), the references to differentiability in my paper can be replaced by references to continuity, provided that the statement of Theorem 16 and of (vi) on p. 330 are changed to

Summary Random associations of points on a graph Let be given a graph consisting of n points, numbered from 1, …, n, and mij joins between points i and j. From this graph r points are chosen at random. This paper deals with the properties of a statistic x, being the number of joins between chosen points. Applications are considered to a test for randomness, and to the order-disorder problem. Analogous results for other statistics and also for the case in which the points are sampled independently of each other, are announced. These results are described in Bloemena, (1960).

Summary Recently a limit theorem has been obtained for the limiting-stationary distribution of a process in which individuals reproduce as in a subcritical Galton-Watson process and are subject to an independent immigration component at each generation. This paper provides a different proof of this theorem, and under slightly weaker conditions. A similar approach is used to obtain a limit form of Taglom's theorem for the ordinary subcritical Galton-Watson process.

Summary Note on the fitting of a function to a large number of observations. The paper deals with various ways in which a set of functions may be chosen to describe a given body of observations, the parameters determining the function being determined by the data. The special case when the functions of the set are given in the form of a table or a graph is emphasized.

Summary The construction of large-size random samples by means of random sampling numbers in the usual way requires much tedious labour. This paper describes a short-cut technique by which artificial samples, of say 500 or 1000, can be obtained in about one tenth of the time. Use is made of previous records of the frequencies of two-digit random sampling numbers; these are called the random sampling frequencies'.

Summary A test against trend for a number of probabilities. This is an expository paper on a test for the equality of a number of probabilities against the alternative hypothesis of a trend, first described by Constance van Eeden and J. Hemelrijk [2]. In section 2 the test is illustrated by means of an example and methods are given to determine the exact distribution of the test statistic under the null-hypothesis and an approximation for this distribution is described. Section 3 gives the general formulation of the test and section 4 contains a generalization. In section 5 methods are given for combining independent tests of this kind.