bluuebunny/crossref_metadata_2025_split huggingface dataset:
A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems
Authors: Miller Donald L. 
Published: October 2008

A branch and bound algorithm for capacitated vehicle routing is described. Lower bounds are derived by relaxing the subtour elimination and vehicle capacity constraints to yield a perfect b-matching problem. Bounds are strengthened by using Lagrange multipliers to enforce subtour elimination and capacity constraints. Computational results are reported for problems taken from the literature for sizes up to 61 vertices. With the exception of the 48 vertex instance (att48.vrp), the algorithm solves all problems in TSPLIB having 51 or fewer vertices. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Inversion of Laplace Transforms of Probability Distributions
Authors: Abate Joseph , Whitt Ward 
Published: October 2008

We present a simple algorithm for numerically inverting Laplace transforms. The algorithm is designed especially for probability cumulative distribution functions, but it applies to other functions as well. Since it does not seem possible to provide effective methods with simple general error bounds, we simultaneously use two different methods to confirm the accuracy. Both methods are variants of the Fourier-series method. The first, building on Dubner and Abate (Dubner, H., J. Abate. 1968. Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. JACM 15 115–123.) and Simon, Stroot, and Weiss (Simon, R. M., M. T. Stroot, G. H. Weiss. 1972. Numerical inversion of Laplace transforms with application to percentage labeled experiments. Comput. Biomed. Res. 6 596–607.), uses the Bromwich integral, the Poisson summation formula and Euler summation; the second, building on Jagerman (Jagerman, D. L. 1978. An inversion technique for the Laplace transform with applications. Bell System Tech. J. 57 669–710 and Jagerman, D. L. 1982. An inversion technique for the Laplace transform. Bell System Tech. J. 61 1995–2002.), uses the Post-Widder formula, the Poisson summation formula, and the Stehfest (Stehfest, H. 1970. Algorithm 368. Numerical inversion of Laplace transforms. Comm. ACM 13 479–490 (erratum: 13 624).) enhancement. The resulting program is short and the computational experience is encouraging. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Efficient Computation of Probabilities of Events Described by Order Statistics and Applications to Queue Inference
Authors: Jones Lee K. , Larson Richard C. 
Published: October 2008

This paper derives recursive algorithms for efficiently computing event probabilities related to order statistics and applies the results in a queue inferencing setting. Consider a set of N i.i.d. random variables in [0, 1]. When the experimental values of the random variables are arranged in ascending order from smallest to largest, one has the order statistics of the set of random variables. Both a forward and a backward recursive O(N3) algorithm are developed for computing the probability that the order statistics vector lies in a given N-rectangle. The new algorithms have applicability in inferring the statistical behavior of Poisson arrival queues, given only the start and stop times of service of all N customers served in a period of continuous congestion. The queue inference results extend the theory of the “Queue Inference Engine” (QIE), originally developed by Larson in 1990 (Larson, R. C. 1990. The queue inference engine: Deducing queue statistics from transactional data. Management Sci. 36(5) 586–601, and 1991. The queue inference engine: Addendum. Management Sci. 37(6) 1062.). The methodology is extended to a third O(N3) algorithm, employing both forward and backward recursion, that computes the conditional average probability (averaged over all N customers in a congestion period) that the in-queue wait is less than t minutes, given the departure time data and assuming first come, first served service. To our knowledge, this result is the first O(N3) exact algorithm for computing points on the in-queue waiting time distribution function, conditioned on the start and stop time data. The paper concludes with an extension to the computation of certain correlations of in-queue waiting times. Illustrative computational results are included throughout. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Revised Stochastic Complementation Algorithm for Nearly Completely Decomposable Markov Chains
Authors: Mattingly R. Bruce 
Published: October 2008

This paper presents a new algorithm which uses stochastic complementation to compute the stationary distribution vector of a nearly completely decomposable (NCD) Markov chain. NCD problems are ill-conditioned, and many methods suffer from loss of accuracy. A formal error analysis and test results from a series of NCD problems are presented which show that the new algorithm computes accurate solutions to this type of problem. Operation counts and timings from experiments are presented which highlight the efficiency of the new algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Bounds and Approximations for Overheads in the Time to Join Parallel Forks
Authors: Downey Peter J. 
Published: October 2008

This paper studies the effects of overheads in massively parallel processing. The execution times for tasks on individual processors are modeled as independent and identically but arbitrarily distributed random variables. The time to execute a process fork is assumed to be distributed exponentially. The main result bounds (in expectation) the overhead time in forking a large number of tasks across n machines and then waiting for the join event. The model used is appropriate for massive parallelism (when n is large): in fact, the bound serves as a heavy traffic limit approached as n→ ∞ and for task times that are large in comparison to the time to execute a fork. In this model, the expected total time to reach the final join consists of a forking overhead that grows linearly with the number of processors n, a time for parallel execution of tasks that decreases in n, and finally a synchronization delay that is a concave sublinear function of ρ = EX/EA, which is the ratio of expected task time to the expected time needed to fork a new process. This overhead function is typically no worse than o(ρ). An interesting aspect of the analysis is that the original problem reduces to a previously studied problem in queueing theory: estimating total end-to-end delay in an infinite-server resequencing system. The new results thus provide new bounds and heavy-traffic approximations (in distribution and in expectation) for the theory of M/GI/∞ resequencing queues. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Matching Identification Problem: A Knowledge Acquisition Approach
Authors: Mehrez Abraham , Steinberg Geoffrey 
Published: October 2008

This paper is concerned with an identification problem of a set of K out of N numbers. Two parties are involved in the identification process, the inquirer and the respondent. The set to be identified is referred to as the chosen subset and it is known only to the respondent. The identification process involves the inquirer who wishes to identify the chosen subset by asking a series of questions. At each question the inquirer selects a subset of K elements out of N, the inquired subset, and receives from the respondent partial information about the number of elements which belongs to both the inquired subset and the chosen subset. The questions continue until the chosen subset is identified. A possible application of the problem is related to learning games. Two types of algorithms, which are independent of each other and aimed at identifying the chosen subset, are presented in this paper. Type I algorithms (uncertainty reduction) select only subsets that have not yet been rejected as being the chosen subset. A linear integer programming model is employed to identify the set of subsets that have not yet been rejected—the uncertainty set. For Type I algorithms two different decision rules are considered to select a subset. Each decision rule selects the elements of the next inquired subset by employing a different probabilistic argument: 1) randomly select the next subset from among the subsets not yet ruled out, or 2) select as the next subset the one whose elements occur most frequently among the subsets not yet ruled out. Type II algorithms (static and dynamic processing) select a subset according to a different principle which allows the inquirer to select a subset that may not belong to the uncertainty set. This is accomplished by marginally interchanging the elements of any two successive subsets. Analytical solutions are provided for algorithms of Type II. Furthermore, a comparison between the two types of algorithms under different measures of performance, such as the expected number of questions (subsets) required to identify the chosen subset, is conducted through a simulation analysis. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Incorporating the Majority Consensus Concurrency Control Mechanism into the Database Allocation Problem
Authors: Ram Sudha , Narasimhan Sridhar 
Published: October 2008

The problem of database allocation incorporating a specific concurrency control mechanism and queuing delays is addressed in this paper. A mathematical model is presented to aid designers in the development of distributed database systems. The model takes into account the pattern of usage of the databases, communication costs in the network, costs for maintaining consistency among the various copies of a database, and storage costs. A solution procedure based on the principle of Lagrangian relaxation is proposed to solve the model. Some analysis of the model is reported along with several useful observations. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Access Path Optimization in Relational Joins
Authors: Gopal Ram D. , Ramesh R. , Zionts Stanley 
Published: October 2008

The objective of access path optimization in relational joins is to minimize the number of pages accessed in performing a join, since the cost of data retrieval from disk accounts for most of the join processing costs. We develop an efficient approach to access path optimization by modeling an access path as a tree traversal process. Two join algorithms are developed using this model. The access path is stored as a compact index relation, which requires absolutely minimal storage. The join is easily materialized by reading the index relation sequentially, and performing the operations coded in its tuples in their serial order. The proposed approach is shown to result in globally minimal page accesses in certain classes of joins. Using a detailed probabilistic analysis and computational study, the proposed approach is shown to be much superior to the state-of-the-art join optimization methods for a general class of joins. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Interval Graph Problems on Reconfigurable Meshes
Authors: Olariu S. , Schwing J. L. , Zhang J. 
Published: October 2008

A graph G is an interval graph if there is a one-one correspondence between its vertices and a family I of intervals, such that two vertices in G are adjacent if and only if their corresponding intervals overlap. In this context, the family I of intervals is referred to as an interval model of G. Recently, a powerful architecture called the reconfigurable mesh has been proposed: in essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. In this paper, we exploit the reconfigurable mesh architecture for the purpose of obtaining constant-time algorithms for a number of computational problems on interval graphs. These problems include finding a maximum size independent set, a minimum clique cover, a minimum size dominating set, a shortest path between any two vertices in G, the diameter and the center of G, as well as Breadth-First Search and Depth-First Search trees for G. Specifically, with an n-vertex interval graph specified by its interval model as input, all our algorithms run in constant time on a reconfigurable mesh of size n × n. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Performance Issues for the Iterative Solution of Markov Decision Processes on Parallel Computers
Authors: Archibald T. W. , McKinnon K. I. M. , Thomas L. C. 
Published: October 2008

This paper analyses the implementation of an iterative solution method for Markov decision processes on distributed memory multiple instruction multiple data (MIMD) parallel processors. To preserve the good convergence properties of this method a parallel algorithm must be synchronous and the aim of this paper is to understand the factors which influence the efficiency of synchronous parallel algorithms for iterative methods. Models are developed for processor communication time, processor calculation time and overall run time which are also appropriate for other iterative methods. Such iterative methods are used in many other problem areas, including dynamic programming and the solution of linear and differential equations. The timing models guide the development of a phased pipeline algorithm. For 60,000 state sparse Markov decision processes using 121 processors, this algorithm gives 60-fold speed-ups relative to the best sparse serial algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Chapter and College News—Proposed New College on the Management of Technological Change
Authors: Gold Bela , Eilon Samuel , Jeckovich Stephen 
Published: October 2008

All those interested in becoming members of a proposed new College on the Management of Technological Change are invited to send a card to the undersigned. The basic objective of the College would be to provide an organized focus within TIMS to encourage the development, presentation, and discussion of concepts, measures, and analytical models as well as empirical studies concerned with managerial aspects of technological changes, including: (a) the evaluation of innovational proposals at successive stages of development, (b) the determinants of adoption decisions as well as of diffusion rates, (c) the appraisal of short- and long-term economic and social effects of various kinds of technologically-rooted innovations, (d) approaches to forecasting and guiding future technological advances, (e) the integration of technological development programs into broader corporate and governmental policies.
Information Systems in Management Science—A Prospectus for Future Columns
Authors: Stern Harry 
Published: October 2008

THE BULLETIN has recently taken on a new form. It was expanded to include articles and columns concerned with the operational problems in using Management Science. The move of this column from Management Science, where it was first published in 1967, prompted me to review its contents and plan a change in its format. I find the columns have followed no pre-set pattern. When unsolicited material was available, it was used, and other topics were selected on the basis of interest to me. Although much of the material still seems relevant, this style leaves some topics undiscussed while others are beaten to death. It also makes it difficult to solicit material. Below are listed a number of topics which will be discussed in later columns. By publishing this list, I have put myself under an obligation to write on a wider range of topics, while giving the reader an opportunity to write on any of the subjects which interest him, as well as to add to the list of potential topics.
Management Science Roundup
Authors: Bucatinsky Julio 
Published: October 2008

We have in Management Science an outstanding scientific journal. Our members can read it and be proud of it. We now must make INTERFACES, and particularly the Management Science Roundup section, a vehicle to abandon our defensive position when it comes to communicating with management. Management Science Roundup is particularly interested in letting people know what it is really like to be out there using a management science approach to solve or help solve management problems in industry, government, education, and society in general. From this point of view, ingenuity, salesmanship, and insight into problem definition are as important as the particular methodology used in solving a given problem. In this issue: —“Special: (1) A systems approach to plant expansion—Rosen, (2) Letters to the editor”; —“Bulletin Board: (1) TIMS meetings, (2) Other meetings/symposia, (3) Summer courses, (4) Personal notes, (5) Notices”; —“Deadlines for future issues of INTERFACES”.
Four Views on Problem Structuring
Authors: Pidd M. , Woolley R. N. 
Published: October 2008

Over the last year or so, we have been attempting to carry out naive research on OR/MS groups. We were a little concerned that though most educational programs do (in the United Kingdom at least) attempt to teach problem structuring, most of this effort was based on little or no systematic knowledge. That is, there seems to be a dearth of empirical research from which lessons could be learned. We found quite a few of the grand old men of OR reflecting on their own experience, but little or no comparative examination of current practice. So we decided to go out and look to see if a rigorous study would be feasible and worthwhile. In addition to our empirical work, we took the time to search through the OR/MS literature to see what could be found therein. The product of that search is reported more fully in another paper [Woolley, R. N., M. Pidd. 1978. Problem structuring in operational research: A review of the literature. Working Paper No. 111, University of Aston Management Centre.]. We thought that readers of Interfaces might be interested in seeing the pattern which we found emerging from the literature.
Facility Location Analysis is Just the Beginning (If you Do It Right)
Authors: Geoffrion Arthur M. , Powers Richard F. 
Published: October 2008

The question How many warehouses should we have: is deceptively simple because a proper answer requires answering, at the same time, a host of interdependent questions. We think that this calls for a comprehensive distribution planning model with optimization capability. Such a managerial tool can be used to deal not only with warehouse location questions, but also with a variety of additional management questions. With this approach, the seed provided by the facility location issue can hear fruit of added utility far beyond original expectations. The authors' experience is that this full potential is seldom achieved in practice without deliberate efforts to remove the block caused by the usual narrow focus on “just” locating facilities.
Seen Elsewhere
Authors: Morgan J. I. 
Published: October 2008

Digests presented: —RECONCILING MANAGEMENT THEORY WITH MANAGEMENT PRACTICE (Business Horizons, February 1977, Vol. 20, No. 1, pp. 38–47) by Stephen P. Robbins (Concordia University). —DECISION MAKING TYPE I AND TYPE II ERROR ANALYSIS (California Management Review, Fall 1977, Vol. XX, No. 1, pp. 81–83), by Philip D. Olson (University of Idaho). —UTILITIES USING MODELING FOR MARKET STRATEGIES (Computer World, June 12, 1978, Vol. XII, No. 24, p. 32), by Marcia Blumenthal. —IMPROVING THE EFFECTIVENESS OF CORPORATE PLANNING (Business Horizons, October 1978, Vol. 21, No. 5, pp. 49–60), by James R. Emshoff (Wharton Applied Research Center) and Ian I. Mitroff (University of Pittsburgh).
Management Science Process—On the Death of Theory Y
Authors: Graham Robert J. 
Published: October 2008

In the February 1978 issue of Interfaces. Walter Nord published an essay in Bye Wynne's “Behavioral Science” column defining some of the problems that arise when attempting to instill Theory Y assumptions in a non-Theory-Y world. The moral for Management Science process seems clear. Management Scientists are often a breed apart and, as such, do not fit the normal corporate image nor respond to the normal corporate incentives. This could make the group seem strange to outsiders and possibly subject to investigation or ridicule by the more standard corporate types. The manager of a project team should thus try to determine if such a problem exists. If it is the case, it would seem important for the project manager to educate the detractors on the fine points of running a Management Science project. Perhaps if they understood, the criticisms will decrease and then pave the way for smoother project work and implementation.
The Fifth Column—Neither a Borrower Nor a Lender be or the Bank Shot Revisited
Authors: Woolsey Gene 
Published: October 2008

The subject of this essay is a problem that a particular banking chain had had the highest level of defaults on car loans in state history during the previous year. They were, naturally, concerned with knowing exactly what had caused this exorbitant loss to make jolly sure that it was not repeated. This sticky problem was shortly thereafter handed to the OR/MS grüppe, and subsequently to the lady asking the question about it. What was clearly needed was some kind of a model that would better accomplish the screening necessary for auto loans than the one they had now. Unfortunately, for a better model you need better data as to why the defaulters defaulted. However, the state legislature, in its infinite wisdom, had recently passed a law that treated such questions from a lending agency to a deadbeat as harassment. To say that this law was enforced with vigor was putting it mildly. Rapidly, banks informed their loan departments that no conversation could be initiated between a bank employee and a defaulter without express approval of a bank officer. The questioner summed up the difficulty very nicely when she stated the problem as follows: “The only way we can come up with a better loan-granting model is to know the reasons why the defaulters defaulted. The only way we can get the necessary information is to ask the defaulters; and the state has, in effect, forbidden us to ask them for it.”
Book Reviews
Authors: Lowe T. J. 
Published: October 2008

Jackson, John H. and Morgan, Cyril P., Organization Theory: A Macro Perspective for Management, Prentice Hall, Inc., 1978—reviewed by Alok K. Chakrabarti Allen, Arnold O., Probability, Statistics, and Queueing Theory with Computer Science Applications, Academic Press, New York, 1978, 390 pp—reviewed by U. Narayan Bhat Bazaraa, Mokhtar S. and Shetty, C. M., Nonlinear Programming, Theory and Algorithms, Wiley, 1979—reviewed by James E. Falk Coyle, R. G., Management System Dynamics, John Wiley and Sons, 1977, xii + 463 pp—reviewed by Michael J. C. Martin Fishman, George S., Principles of Discrete Event Simulation, John Wiley and Sons, Inc., New York, 1978, 514 pp—reviewed by Lee W. Schruben Gupta, Madan N., Saridis, George N. and Gaines, Brian R. (Eds.), Fuzzy Automata and Decision Processes, North Holland, New York, 1977, 496 pp—reviewed by Steven Nahmias Keen, Peter G. W. and Morton, Michael S. Scott, Decision Support Systems: An Organizational Perspective, Addison-Wesley, 1978, 264 pp—reviewed by John S. Rose Kilmann, Ralph H., Social Systems Design-Normative Theory and the MAPS Design Technology, Elsevier North-Holland Inc., 52 Vanderbilt Avenue, New York, 1977, 317 pp—reviewed by Donald C. King and Ann C. Seror