639 results
Search Results
2. APPLIED STATISTICS ALGORITHMS SECTION.
- Subjects
MATHEMATICS ,ALGORITHMS ,PAPER ,COMPUTER programming ,TECHNICAL specifications - Abstract
The article presents information on the publication of a book "Applied Statistics, Algorithms," relevant to statistics, by the Royal Statistical Society in cooperation with the Science Research Council's Working Party on Statistical Computing. A policy statement describing the editorial policy appears in "Applied Statistics," Vol. 1. No. 1 (1968). A support paper describing the expected contents of the external specification and making recommendation for the layout of algorithms and for programming strategy will appear in the following issue.
- Published
- 1968
3. A COMMENT ON A PAPER OF MAXWELL.
- Author
-
Sidney, Jeffrey B.
- Subjects
JOB shops management ,INTEGER programming ,MATHEMATICAL programming ,PRODUCTION management (Manufacturing) ,ALGORITHMS ,LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL models ,MANAGEMENT science research ,OPERATIONS research - Abstract
The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.
- Published
- 1972
- Full Text
- View/download PDF
4. Index Ranges for Matrix Calculi.
- Author
-
Bayer, R., Witzgall, C., and Gries, D.
- Subjects
MATHEMATICAL analysis ,ALGORITHMS ,DATA structures ,COMPUTER programming ,ELECTRONIC file management ,ELECTRONIC data processing - Abstract
The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
5. A Computer System for Transformational Grammar.
- Author
-
Bobrow, D. G. and Friedman, Joyce
- Subjects
COMPUTER systems ,GENERATIVE grammar ,IBM computers ,PROGRAMMING languages ,ALGORITHMS ,COMPUTER industry ,COMPUTATIONAL linguistics - Abstract
A comprehensive system for transformational grammar has been designed and implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's Aspects of the Theory of Syntax. The major innovations include a full, formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, an extended definition of analysis, and simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the general attitudes underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider some particular aspect of the system in detail. [ABSTRACT FROM AUTHOR]
- Published
- 1969
6. Letters to the Editor.
- Author
-
Parnas, David L., deVeber, Jeffrey L., Rice, John R., and Dijkstra, Edsger W.
- Subjects
LETTERS to the editor ,CONFERENCES & conventions ,COMPUTERS ,ALGORITHMS ,ALGEBRA ,COORDINATES - Abstract
Presents several letters to the editor about the computing machinery. Dissatisfaction with the quality and nature of the average technical paper presented at the Joint Computer Conferences; Comment on the article "One-Pass Compilation of Arithmetic Expressions for a Parallel Processor," by Harold S. Stone; Use of a coordinate system or characteristic indices for the progress of an algorithm.
- Published
- 1968
- Full Text
- View/download PDF
7. COMMENTS ON A PAPER BY ROMESH SAIGAL: "A CONSTRAINED SHORTEST ROUTE PROBLEM".
- Author
-
Rosseel, Marc
- Subjects
LINEAR programming ,ALGORITHMS ,VECTOR algebra ,COMPUTER programming ,CONSTRAINTS (Physics) ,DYNAMIC programming ,MATRICES (Mathematics) ,DISTANCES - Abstract
The article presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network (N, A) with distances c(i, j). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty. A special feature of this linear program is that there can never be a loop in the basis, because the vectors corresponding to the variables of a loop are linearly dependent. The last comment is related to the dynamic programming algorithm. One is allowed to pass through a node more than once in the shortest route . The proposed method for solving this program consists of converting it into a shortest route problem containing exactly q arcs. But for some arbitrary reason, the dynamic program is formulated in such a way that one can never have starting node 1 more than once in the final solution.
- Published
- 1968
- Full Text
- View/download PDF
8. Generating Parsers for Affix Grammars.
- Author
-
Crowe, David
- Subjects
AFFIXES (Grammar) ,MORPHEMICS ,PARSING (Computer grammar) ,COMPUTATIONAL linguistics ,PROGRAMMING languages ,ALGORITHMS ,GRAMMAR - Abstract
Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
9. Implementing Clenshaw-Curtis Quadrature, I Methodology and Experience.
- Author
-
timlake, W. P. and Gentleman, W. Morven
- Subjects
NUMERICAL integration ,COMPUTER systems ,ALGORITHMS ,COMPUTER science ,NUMERICAL analysis ,ARITHMETIC - Abstract
Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive. This paper is in two parts; a companion paper, "II Computing the Cosine Transformation," shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme. [ABSTRACT FROM AUTHOR]
- Published
- 1972
10. Implementing Clenshaw-Curtis Quadrature, II Computing the Cosine Transformation.
- Author
-
Tirniake, W. P. and Gentleman, W. Morven
- Subjects
NUMERICAL integration ,COMPUTER systems ,ALGORITHMS ,NUMERICAL analysis ,COMPUTER science ,ARITHMETIC - Abstract
In a companion paper to this, "I Methodology and Experiences," the automatic Clenshaw-Curtis quadrature scheme was described and how each quadrature formula used in the scheme requires a cosine transformation of the integrand values was shown. The high cost of these cosine transformations has been a serious drawback in using Clenshaw-Curtis quadrature. Two other problems related to the cosine transformation have also been troublesome. First, ... conventional computation of the cosine transformation by recurrence relation is numerically unstable, particularly at the low frequencies which have the largest effect upon the integral. Second, in case the automatic scheme should require refinement of the sampling, storage is required to save the integrand values after the cosine transformation is computed. This second part of the paper shows how the cosine transformation can be computed by a modification of the fast Fourier transform and all three problems overcome. The modification is also applicable in other circumstances requiring cosine or sine transformations, such as polynomial interpolation through the Chebyshev points. [ABSTRACT FROM AUTHOR]
- Published
- 1972
11. Scheduling to Reduce Conflict in Meetings.
- Author
-
Grimes, Joseph E. and Emery, J. C.
- Subjects
PRODUCTION scheduling ,MANAGEMENT ,SPACETIME ,GRAPHIC methods ,CONSTRAINTS (Physics) ,ALGORITHMS - Abstract
Conflicts in scheduling can be treated as defining an undirected linear graph independently of the relation of the activities in conflict to additional constraints of time and space. Each connected component of such a graph, which can be found by on algorithm described by Gotlieb and Corneil, corresponds to a set of events that must be scheduled at different times. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
12. A PRIMAL ALGORITHM TO SOLVE NETWORK FLOW PROBLEMS WITH CONVEX COSTS.
- Author
-
Weintraub, Andres
- Subjects
CASH flow ,DIRECT costing ,MANAGEMENT science ,CONVEX functions ,CASH management ,MANAGEMENT ,ALGORITHMS ,STOCHASTIC convergence ,MANAGERIAL economics - Abstract
The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
13. ON NONLINEAR FRACTIONAL PROGRAMMING.
- Author
-
Dinkelbach, Werner
- Subjects
FRACTIONAL integrals ,NONLINEAR programming ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,PARAMETER estimation ,QUADRATIC programming ,CONCAVE functions ,CONVEX functions ,POLYHEDRAL functions ,NUMERICAL solutions to Lagrange equations - Abstract
The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
14. ON SOME WORKS OF KANTOROVICH, KOOPMANS AND OTHERS.
- Author
-
Charnes, A. and Cooper, W. W.
- Subjects
INDUSTRIAL management ,MANAGEMENT science ,LINEAR programming ,GAME theory ,MANAGEMENT games ,DECISION making ,DECISION theory ,ALGORITHMS ,RANDOM variables - Abstract
Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.
- Published
- 1962
- Full Text
- View/download PDF
15. AN EVALUATION OF THE EMPIRICAL SIGNIFICANCE OF OPTIMAL SEEKING ALGORITHMS IN PORTFOLIO SELECTION.
- Author
-
PORTER, R. BURR and BEY, ROGER P.
- Subjects
PORTFOLIO management (Investments) ,INVESTMENT analysis ,PORTFOLIO performance ,SECURITIES ,INVESTMENTS ,ALGORITHMS - Abstract
The mean-variance (EV) portfolio selection rule has recently been challenged by a new procedure referred to as the Stochastic Dominance Rule (SD), which is touted as being theoretically and empirically superior. However, the SD procedure suffers from at least one technical deficiency not associated with the EV model--the lack of a search algorithm that builds efficient combinations of assets. The purpose of this paper is to evaluate the significance of this problem and to consider procedures for its alleviation. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
16. COMMENTS ON A PAPER BY M. L. WOLFSON: 'SELECTING THE BEST LENGTHS TO STOCK'
- Author
-
Cohen, Gerald D.
- Subjects
STOCK prices ,STOCKS (Finance) ,DYNAMIC programming ,NONLINEAR programming ,INTEGER programming ,LINEAR programming ,ALGORITHMS - Abstract
This article presents comments on a paper by M.L. Wolfson related to selecting the best lengths to stock. The problem considered in the paper by Wolfson is a classic specimen of the type ideally structured for direct and practical solution by dynamic programming. The author's algorithm, given in the paper, is in the spirit of this method, but its understanding could be greatly simplified if put into the recursive formalism of dynamic programming.
- Published
- 1966
- Full Text
- View/download PDF
17. A Nonrecursive Method of Syntax Specification.
- Author
-
Carr, III, John W., Weiland, Jerome, and Knuth, D. E.
- Subjects
FORTRAN II ,PROGRAMMING languages ,MATHEMATICAL notation ,ALGORITHMS ,COMPUTER software ,LINEAR systems - Abstract
The use of the Kleene regular expression notation for describing algebraic language syntax, in particular of ALGOL is described in this paper. A FORTRAN II computer program for carrying out the elimination algorithm of Gorn, similar to Gaussian elimination for linear systems of algebraic equations, is described. This was applied to numerous smaller languages, including some sublanguages of ALGOL. A hand calculation result of the application of the algorithm to all of ALGOL is given, thus expressing the Revised ALGOL 1960 syntax in completely nonrecursive terms, as far as its context-free portion is concerned. This description in many ways is far more intuitively understood than the previous recursive description, it is suggested. The paper also includes results of the machine program, which does not include a simplification algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
18. General Performance Analysis of Key-to-Address Transformation Methods Using an Abstract File...
- Author
-
Lum, V. Y. and Morgan, H.
- Subjects
COMPUTER algorithms ,PERFORMANCE evaluation ,MATHEMATICAL transformations ,ALGORITHMS ,COMPUTER files ,PROBABILITY theory - Abstract
This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file arc assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
19. Asymptotic Linear Programming.
- Author
-
Jeroslow, Robert G.
- Subjects
LINEAR programming ,ALGORITHMS ,MATHEMATICAL functions ,PRODUCTION scheduling ,MATHEMATICAL programming ,MATHEMATICAL models - Abstract
This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t
0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0 , the second for t»t0 )]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn ↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]- Published
- 1973
- Full Text
- View/download PDF
20. Letters to the Editor.
- Author
-
Ignizio, James P.
- Subjects
LETTERS to the editor ,ALGORITHMS - Abstract
This letter calls attention to the problems of validating the claim made for algorithms in published papers, and proposes a system for review that will validate such claims thoroughly before publication. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
21. Some Properties of Generalized Concave Functions.
- Author
-
Thompson Jr., W. A. and Parke, Darrel W.
- Subjects
CONCAVE functions ,REAL variables ,MATHEMATICAL programming ,COMPLEX variables ,ALGORITHMS ,FUNCTIONAL equations ,MATHEMATICAL optimization ,OPERATIONS research - Abstract
This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
22. CHANCE CONSTRAINED PROGRAMMING WITH JOINT CONSTRAINTS.
- Author
-
Miller, Bruce L. and Wagner, Harvey M.
- Subjects
LINEAR programming ,DYNAMIC programming ,MATHEMATICAL programming ,LOGARITHMIC functions ,NONLINEAR programming ,ALGORITHMS ,OPERATIONS research - Abstract
This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
23. DISCOUNTED MARKOV PROGRAMMING IN A PERIODIC PROCESS.
- Author
-
Riis, Jens Ove
- Subjects
MARKOV processes ,PROBABILITY theory ,ALGORITHMS ,MATHEMATICAL programming ,ITERATIVE methods (Mathematics) - Abstract
This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of R. A. HOWARD's policy-iteration technique for stationary Markov processes. A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
24. DISCOUNTED MARKOV PROGRAMMING IN A PERIODIC PROCESS.
- Author
-
Riis, Jens Ove
- Subjects
MARKOV processes ,ALGORITHMS ,STOCHASTIC processes ,ITERATIVE methods (Mathematics) ,PROBABILITY theory ,OPERATIONS research - Abstract
This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of B. A. HOWARD'S policy-iteration technique for stationary Markov processes, A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
25. THE MULTI-INDEX PROBLEM.
- Author
-
Haley, K. B.
- Subjects
TRANSPORTATION problems (Programming) ,TRANSPORTATION ,ALGORITHMS ,PROBLEM solving ,LINEAR programming ,MATHEMATICAL inequalities ,SIMPLEXES (Mathematics) ,OPERATIONS research ,EQUATIONS - Abstract
The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]
- Published
- 1963
- Full Text
- View/download PDF
26. A TIME-SHARING COMPUTER PROGRAM FOR THE SOLUTION OF THE MULTIPLE CRITERIA PROBLEM.
- Author
-
Dyer, James S.
- Subjects
MULTIPLE criteria decision making ,TIME-sharing computer systems ,INTERACTIVE computer systems ,HUMAN-machine systems ,DECISION making ,PROBLEM solving research ,COMPUTER software ,COMPUTER programming ,ALGORITHMS - Abstract
This note presents a description of a time-sharing computer program written to implement a man-machine interactive algorithm for the solution of the multiple criteria problem. The interactive algorithm was suggested in a recent paper by Geoffrion, "Vector Maximal Decomposition Programming," Working Paper No. 164, Western Management Science Institute, University of California, Los Angeles, September 1970. A unique feature of this program is the man-machine dialog which obtains information from the decision-maker through a series of simple, ordinal comparisons. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
27. Algorithms.
- Author
-
Paciorek, Kathleen A. and Fosdick, L. D.
- Subjects
ALGORITHMS ,COMPUTERS ,ELECTRONIC systems ,FORTRAN ,COMPUTER programming - Abstract
The article presents several research papers relating to algorithms. The paper "Greatest Common Divisor of n Integers and Multipliers" presents an algorithm which calculates the greatest common divisor, IGCD, of n integers. Details of the method and comparisons to other algorithms are also given. The algorithm is a new version of the Euclidean algorithm for n integers. The n-1 calculations of the greatest common divisor of two integers is accomplished by means of a modified version of the Blankinship algorithm. The paper "Exponential Integral Ei (x)" presents the results of one phase of research carried out at the Jet Propulsion Laboratory, California Institute of Technology, under Contract NAS7-100, sponsored by the National Aeronautics and Space Administration. It presents an algorithm which was compiled and executed without any modification on a UNIVAC 1108 computer. An unfortunate precedent has been set in several recent algorithms of using an illegal FORTRAN construction.
- Published
- 1970
28. Context-Sensitive Parsing.
- Author
-
Woods, William A. and Bobrow, D. G.
- Subjects
PARSING (Computer grammar) ,ALGORITHMS ,COMPUTATIONAL linguistics ,MULTILINGUAL computing ,COMPUTER algorithms ,LOOPS (Group theory) - Abstract
This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
29. An Algorithm for the Construction Of Bounded-Context Parsers.
- Author
-
Loeckx, Jacques and Reynolds, J. C.
- Subjects
PARSING (Computer grammar) ,ALGORITHMS ,COMPUTATIONAL linguistics ,FORMAL languages ,COMPILERS (Computer programs) ,COMPUTER software - Abstract
An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists. In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free gram- mar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a Context-free grammar ore defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes, In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
30. AIgorithms.
- Author
-
Fosdick, LLoyd D.
- Subjects
COMPUTER algorithms ,FACTOR analysis ,ALGORITHMS ,ANALYSIS of variance ,STATISTICAL correlation ,MULTIVARIATE analysis - Abstract
The article presents comments on several algorithms. The algorithms offer information on factorial analysis of variance, shortest-path forest with topological ordering, permanent function of a square matrix I and II, generation of random permutations, complex error function, associated legendre functions of the first kind for real or imaginary arguments, computation of Fourier coefficients, generalized least squares fit by orthogonal polynomials and generation of permutations in pseudolexicographic order.
- Published
- 1969
31. A Graph Formulation of a School Scheduling Algorithm.
- Author
-
Salazar, A. and Oakford, R. V.
- Subjects
ALGORITHMS ,SCHOOL schedules ,GRAPH theory ,APPROXIMATION theory ,SET theory ,CURRICULUM - Abstract
The problem classically titled "The Examination Schedule Problem" takes various forms in the literature. Most of these formulations can be presented in the terminology of classical Network Theory. One such formulation is: Given a nondirected network, partition its nodes into a minimal number of subsets such that no two members of the same subset are connected by an An obvious lower limit to this number is the size of the largest strongly connected subgraph. Kirchgassner proved that an upper limit is this size plus one. One logical extension of the previous work is the introduction of variable length examinations where W(I) is the number of periods for exam I. The object of this paper is to generalize the definition of largest strongly connected subgraph to include the weighting of nodes, to present an approximate algorithm which usually finds the largest strongly connected subgraph, and to discuss the application of this algorithm to the solution of school scheduling and exam scheduling problems. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
32. A NOTE ON CORRELATED ERRORS IN REPEATED MEASUREMENTS.
- Author
-
Wiley, James A. and Wiley, Mary Glenn
- Subjects
STATISTICAL correlation ,MEASUREMENT errors ,ALGORITHMS ,ATTENUATION (Physics) ,MATHEMATICAL variables ,ESTIMATION theory - Abstract
This paper considers a test score model in which the true score and the measurement error are autocorrelated. After some preliminary remarks on corrections for attenuation, the paper focuses on the three-wave ease (t = 1, 2, 3), demonstrating identifiability, showing an estimation algorithm, and providing a numerical illustration. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
33. Production Planning for a Stochastic Demand Process.
- Author
-
Gonedes, Nicholas J. and Lieber, Zvi
- Subjects
PRODUCTION planning ,ECONOMIC demand ,STOCHASTIC processes ,ALGORITHMS ,PLANNING ,PRODUCTION engineering ,INVENTORY control - Abstract
This paper deals with planning production of a single good over a prescribed finite interval of time [0, T]. The costs considered within the problem are production and holding costs; holding costs are incurred for negative inventory (caused by backlogged sales) and positive inventory (caused by production in excess of demand). The demand for the product is treated as a stochastic process. Problem formulation and optimization use tools from continuous-time stochastic variational calculus and control theory. Among its results, the paper proves the uniqueness of the optimal solution and provides an algorithm for the problem. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
34. The Elementary Redundancy-Optimization Problem: A Case Study in Probabilistic Multiple-Goal Programming.
- Author
-
Hendrix, G. G. and Stedry, A. C.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL programming ,LINEAR programming ,PROBABILITY theory ,ALGORITHMS ,INTEGER programming ,SYSTEM analysis - Abstract
This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
35. The Optimal Location of Nuclear-Power Facilities in the Pacific Northwest.
- Author
-
Dutton, Ron, Hinman, George, and Millham, C. B.
- Subjects
NUCLEAR power plant location ,NUCLEAR power plants ,INDUSTRIAL location ,MATHEMATICAL optimization ,BRANCH & bound algorithms ,TRANSPORTATION ,ALGORITHMS ,GROWTH rate - Abstract
This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
36. A Generated Cut for Primal Integer Programming.
- Author
-
Arnold, Larry R. and Bellmore, Mandell
- Subjects
INTEGER programming ,LINEAR programming ,ALGORITHMS ,MATHEMATICAL optimization ,ITERATIVE methods (Mathematics) ,STOCHASTIC processes - Abstract
This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
37. Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory.
- Author
-
Gelders, L. and Kicindorfer, P. R.
- Subjects
PRODUCTION scheduling ,SCHEDULING ,DECISION making ,OVERTIME ,ALGORITHMS ,TARDINESS ,COST ,JOB shops - Abstract
This paper presents a formal model of the one-machine job-shop scheduling problem with variable capacity. Its primary interest focuses on the trade-off between overtime and detailed scheduling costs. The scheduling problem considered is minimizing the sum of weighted tardiness and weighted flow-time costs for a given capacity plan (i.e., a given overtime plan). The paper generalizes sequence-theory results to this case where possible, analyzes various lower-bounding structures for the problem, outlines a preliminary branch-and-bound algorithm, and illustrates several interesting features of the algorithm and bounding structures by an example. Extensions of the results to more complex environments are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
38. A Mathematical Model for Simultaneously Determining the Optimal Brand-Collection and Display-Area Allocation.
- Author
-
Anderson, Evan E. and Amato, Henry N.
- Subjects
ALGORITHMS ,RESOURCE allocation ,BRAND name products ,BUSINESS names ,RETAIL industry ,PROFIT ,CONSUMER preferences - Abstract
This paper addresses a fundamental short-run resource-allocation problem confronting retail distribution: simultaneously finding the specific brands, from many, that should be displayed, and the amount of retail product-display area that should be assigned to these brands, in order to maximize the retail institution's profit. The paper decomposes total market demand according to the various levels of brand preference that could conceivably exist in final markets, and then, employs an algorithm, similar to the one used to solve the fixed-charge problem, to find the optimal brand mix and display-area allocation. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
39. ON THE MAXIMIZATION OF THE GEOMETRIC MEAN WITH LOGNORMAL RETURN DISTRIBUTION.
- Author
-
Elton, Edwin J. and Gruber, Martin J.
- Subjects
LOGNORMAL distribution ,DISTRIBUTION (Probability theory) ,ALGORITHMS ,VARIANCES ,GEOMETRIC programming ,PORTFOLIO management (Investments) ,ECONOMIC equilibrium ,METHODOLOGY ,RATE of return - Abstract
In this paper we discuss the relevancy of the geometric mean as a portfolio selection criteria. A procedure for finding that portfolio with the highest geometric mean when returns on portfolios are lognormally distributed is presented. The development of this algorithm involves a proof that the portfolio with maximum geometric mean lies on the efficient frontier in arithmetic mean variance space. This finding has major implications for the relevancy of much of portfolio and general equilibrium theory. These implications are explored. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
40. APPLICATION OF QUASI-INTEGER PROGRAMMING TO THE SOLUTION OF MENU PLANNING PROBLEMS WITH VARIABLE PORTION SIZE.
- Author
-
Armstrong, Ronald D. and Sinha, Prabhakant
- Subjects
MENU design (Printed ephemera) ,MATHEMATICAL programming ,ALGORITHMS ,INTEGER programming ,CAPITAL budget ,MENUS ,BRANCH & bound algorithms ,FOOD service research ,PLANNING - Abstract
This paper presents the application of a modified mixed-integer programming algorithm to plan menus in which the portion size of the menu items can vary over a specified positive range. Previous mathematical programming formulations of menu planning problems have either required the variables representing menu items to be bivalent, or have formulated the problem with food groups as decision variables and no integer requirements at all. The former gives rise to a zero-one programming problem and the latter to a "feed-mix" problem. In many instances, a more realistic formulation would require that if a menu item is offered, its portion size must be between a specified upper and lower bound. Although this paper addresses itself chiefly to menu planning, it is readily seen that problems in capital budgeting may be tractable with a similar formulation. It is shown how a branch-and-bound algorithm for mixed-integer programming of the type proposed by Beale and Tomlin can be modified to solve the quasi-integer programming problem resulting from a variable portion size formulation of menu planning problems. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
41. DETERMINATION OF OPTIMUM PACKAGING FREQUENCY OF ITEMS JOINTLY REPLENISHED.
- Author
-
Goyal, S. K.
- Subjects
MANUFACTURING processes ,PACKAGING research ,OVERHEAD costs ,VARIABLE costs ,INVENTORY management systems ,MATHEMATICAL models ,ALGORITHMS ,ECONOMIC lot size - Abstract
This paper presents a systematic procedure for obtaining the optimum packaging frequencies for a number of items which are manufactured jointly but packaged individually immediately after manufacture. The method described in the paper is equally applicable to those problems where the optimum purchasing policy is to be obtained for a number of items procured from a single supplier. An example involving twenty jointly replenished items is solved to illustrate the procedure given in the paper. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
42. SOLVING THE "MARKETING MIX" PROBLEM USING GEOMETRIC PROGRAMMING.
- Author
-
Balachandran, V. and Gensch, Dennis H.
- Subjects
MARKETING mix ,GEOMETRIC programming ,BUSINESS planning ,MATHEMATICAL programming ,LINEAR programming ,MARKETING research ,ALGORITHMS ,MATHEMATICAL optimization ,REGRESSION analysis - Abstract
This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
43. Incorporating Origin Shifts into the QR Algorithm for Symmetric Tridiagonal Matrices.
- Author
-
Stewart, G. W. and Timlake, W. P.
- Subjects
EIGENVALUES ,ALGORITHMS ,MATRICES (Mathematics) ,COMPUTER programming ,MATHEMATICAL functions ,STOCHASTIC convergence - Abstract
The QR iteration for the eigenvalues of a symmetric tridiagonal matrix can be accelerated by incorporating a sequence of origin shifts. The origin shift may be either subtracted directly from the diagonal elements of the matrix or incorporated by means of an implicit algorithm. Both methods have drawbacks: the direct method can unnecessarily degrade small eigen-values, while the implicit method can effectively loose the shift and thereby retard the convergence. This paper presents a new method which has neither drawback. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
44. News.
- Subjects
ORGANIZATIONAL name changes ,CONFERENCES & conventions ,MATHEMATICS software ,ALGORITHMS - Abstract
The article offers news briefs related to the Association for Computing Machinery (ACM) in the U.S. The United States of America Standards Institute Inc. (USASI) changed its name to the American National Standards Institute (ANSI). A symposium on mathematical software will be held at Purdue University in West Lafayette, Indiana will be held from April 1 -3, 1970. The Second Annual ACM Symposium on Theory of Computing will be held in Northampton Massachusetts from May 4-6, 1970.
- Published
- 1969
45. On Compiling Algorithms for Arithmetic Expressions.
- Author
-
Nakata, Ikuo
- Subjects
COMPILERS (Computer programs) ,COMPUTER arithmetic ,FORTRAN IV ,PROGRAMMING languages ,ALGORITHMS ,BINARY number system - Abstract
This paper deals with algorithms concerning arithmetic expressions used in a FORTRAN IV compiler for a HITAC.5020 computer having n accumulators. The algorithms generate an object code which minimizes the frequency of storing and recovering the partial results of the arithmetic expressions in cases where there are several accumulators. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
46. A Note on Linear Programming Algorithm Design: A Combinatorial Problem.
- Author
-
Roes, P. B. M.
- Subjects
COMPUTER storage devices ,LINEAR programming ,DISTRIBUTION (Probability theory) ,ALGORITHMS ,MAGNETIC tapes ,MATHEMATICAL models - Abstract
As linear programming models grow bigger and bigger in size, much actual data that must be memorized is often put on magnetic tape or disk, and consequently there is an improportionately fast rise in the consumption of computer time. To cut down this expense, on ever increasing effort Is mode to design more efficient algorithms. This paper is meant to support the effort. If is attempted to find some characteristics of the way pivot column is found. The number of repetitions of a certain transfer of data from tape to core memory is considered. After some simplification, the problem is restated in a general way. The generating function of the probability distribution and the moment generating function of the number of repetitions is found. Asymptotic formulas are given for the moments using result from a paper of S. Narumi [1]. The results may be applied to write very efficient routines that search for an extreme value in a table. Formulas provide a means of calculating the computer timings in this case. [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
47. The Optimal Control of Partially Observable Markov Processes over a Finite Horizon.
- Author
-
Smallwood, Richard D. and Sondik, Edward J.
- Subjects
MARKOV processes ,STOCHASTIC processes ,MATHEMATICAL models ,DISCRETE-time systems ,SYSTEM analysis ,MATHEMATICAL functions ,ALGORITHMS - Abstract
This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
48. The Rearrangement of Items in a Warehouse.
- Author
-
Christofides, Nicos and Colloff, I.
- Subjects
WAREHOUSE management ,WAREHOUSES ,ALGORITHMS ,FACTORIES ,CYCLES ,PLANT layout ,COMMERCIAL buildings ,PHYSICAL distribution of goods - Abstract
This paper is concerned with finding the optimal way of rearranging items in a warehouse from their initial positions to their desired final locations. Such a rearrangement may become necessary because of changes in the relative demand for each item, with the result that what were once fast-moving items at the 'front' end of the warehouse, are now only slow-moving ones that must be moved towards the 'rear.' Although the problem, as treated in this paper, is addressed to the rearrangement of items in a warehouse, many other applications come immediately to mind, such as the reorganization of the layout of open-plan orates and factories. The paper gives a two-stage algorithm that produces the sequence of item movements necessary to achieve the desired rearrangement and incur the minimum cost (or time) spent in the rearranging process; the result is optimal in the restricted case where the rearrangement must be done in a number of cycles each one being of a short time duration (the case, for example, if the warehouse were to remain operative during the rearrangement). [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
49. Maximal, Lexicographic, and Dynamic Network Flows.
- Author
-
Minieka, Edward
- Subjects
ALGORITHMS ,LEXICOGRAPHY ,SCHEDULING ,ENCYCLOPEDIAS & dictionaries ,ALGEBRA ,FOUNDATIONS of arithmetic - Abstract
This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources nd this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies FORD AND FULKERSON'S maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earnest arrival schedule. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
50. The Use of Cuts in Complementary Programming.
- Author
-
Ibaraki, Toshihide
- Subjects
MATHEMATICAL programming ,LINEAR programming ,MATRICES (Mathematics) ,VECTOR analysis ,ALGORITHMS ,FUNCTIONAL equations ,MATHEMATICAL optimization ,OPERATIONS research - Abstract
A complementary programming problem is a linear programming problem with the additional restriction that x
p xq =0 holds for each specified pair (xp , xq ). This paper obtains constraints called C-cuts from the restriction xp xq =0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported. [ABSTRACT FROM AUTHOR]- Published
- 1973
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.