Applied Probability-Computer Science: The Interface Volume 1


Book Description

These two volumes are the Proceedings of the first special interest meeting instigated and organized by the joint Technical Section and College in Applied Probability of ORSA and THlS. This meeting, which took place January 5-7, 1981 at Florida Atlantic University in Boca Raton, Florida, had the same name as these Proceedings: Applied Probability-Computer Science, the Interface. The goal of that conference was to achieve a meeting of, and a cross fertilization between, two groups of researchers who, from different starting points, had come to work on similar problems, often developing similar methodologies and tools. One of these groups are the applied probabilists, many of whom consider their field an offspring of mathematics, and who find their motivation in many areas of application. The other is that group of computer scientists who, over the years, have found an increasing need in their work for the use of probabilistic models. The most visible area of common methodology between these two groups is networks of queues, Hhich by itself could have been the theme of an entire conference. FunctionQl areas which are, or are becoming, sources of exciting problems are computer performance analysis, data base analysis, analysis of communication protocols, data networks, and mixed voice-data telephone networks. The reader can add to this list by going through the papers in these Proceedings.







Coding, Cryptography and Combinatorics


Book Description

It has long been recognized that there are fascinating connections between cod ing theory, cryptology, and combinatorics. Therefore it seemed desirable to us to organize a conference that brings together experts from these three areas for a fruitful exchange of ideas. We decided on a venue in the Huang Shan (Yellow Mountain) region, one of the most scenic areas of China, so as to provide the additional inducement of an attractive location. The conference was planned for June 2003 with the official title Workshop on Coding, Cryptography and Combi natorics (CCC 2003). Those who are familiar with events in East Asia in the first half of 2003 can guess what happened in the end, namely the conference had to be cancelled in the interest of the health of the participants. The SARS epidemic posed too serious a threat. At the time of the cancellation, the organization of the conference was at an advanced stage: all invited speakers had been selected and all abstracts of contributed talks had been screened by the program committee. Thus, it was de cided to call on all invited speakers and presenters of accepted contributed talks to submit their manuscripts for publication in the present volume. Altogether, 39 submissions were received and subjected to another round of refereeing. After care ful scrutiny, 28 papers were accepted for publication.




Analytical Performance Modeling for Computer Systems


Book Description

This book is an introduction to analytical performance modeling for computer systems, i.e., writing equations to describe their performance behavior. It is accessible to readers who have taken college-level courses in calculus and probability, networking, and operating systems. This is not a training manual for becoming an expert performance analyst. Rather, the objective is to help the reader construct simple models for analyzing and understanding the systems in which they are interested. Describing a complicated system abstractly with mathematical equations requires a careful choice of assumptions and approximations. These assumptions and approximations make the model tractable, but they must not remove essential characteristics of the system, nor introduce spurious properties. To help the reader understand the choices and their implications, this book discusses the analytical models in 20 research papers. These papers cover a broad range of topics: processors and disks, databases and multimedia, worms and wireless, etc. An Appendix provides some questions for readers to exercise their understanding of the models in these papers. Table of Contents: Preliminaries / Concepts and Little's Law / Single Queues / Open Systems / Markov Chains / Closed Systems / Bottlenecks and Flow Equivalence / Deterministic Approximations / Transient Analysis / Experimental Validation and Analysis / Analysis with an Analytical Model




Applied Probability and Stochastic Processes


Book Description

Applied Probability and Stochastic Processes is an edited work written in honor of Julien Keilson. This volume has attracted a host of scholars in applied probability, who have made major contributions to the field, and have written survey and state-of-the-art papers on a variety of applied probability topics, including, but not limited to: perturbation method, time reversible Markov chains, Poisson processes, Brownian techniques, Bayesian probability, optimal quality control, Markov decision processes, random matrices, queueing theory and a variety of applications of stochastic processes. The book has a mixture of theoretical, algorithmic, and application chapters providing examples of the cutting-edge work that Professor Keilson has done or influenced over the course of his highly-productive and energetic career in applied probability and stochastic processes. The book will be of interest to academic researchers, students, and industrial practitioners who seek to use the mathematics of applied probability in solving problems in modern society.




Queueing Networks


Book Description

This handbook aims to highlight fundamental, methodological and computational aspects of networks of queues to provide insights and to unify results that can be applied in a more general manner. The handbook is organized into five parts: Part 1 considers exact analytical results such as of product form type. Topics include characterization of product forms by physical balance concepts and simple traffic flow equations, classes of service and queue disciplines that allow a product form, a unified description of product forms for discrete time queueing networks, insights for insensitivity, and aggregation and decomposition results that allow sub networks to be aggregated into single nodes to reduce computational burden. Part 2 looks at monotonicity and comparison results such as for computational simplification by either of two approaches: stochastic monotonicity and ordering results based on the ordering of the process generators, and comparison results and explicit error bounds based on an underlying Markov reward structure leading to ordering of expectations of performance measures. Part 3 presents diffusion and fluid results. It specifically looks at the fluid regime and the diffusion regime. Both of these are illustrated through fluid limits for the analysis of system stability, diffusion approximations for multi-server systems, and a system fed by Gaussian traffic. Part 4 illustrates computational and approximate results through the classical MVA (mean value analysis) and QNA (queueing network analyzer) for computing mean and variance of performance measures such as queue lengths and sojourn times; numerical approximation of response time distributions; and approximate decomposition results for large open queueing networks. spanPart 5 enlightens selected applications as spanloss networks originating from circuit switched telecommunications applications, capacity sharing originating from packet switching in data networks, and a hospital application that is of growing present day interest. spanThe book shows that spanthe intertwined progress of theory and practicespan will remain to be most intriguing and will continue to be the basis of further developments in queueing networks.




Multivariate Statistical Simulation


Book Description

Provides state-of-the-art coverage for the researcher confronted with designing and executing a simulation study using continuous multivariate distributions. Concise writing style makes the book accessible to a wide audience. Well-known multivariate distributions are described, emphasizing a few representative cases from each distribution. Coverage includes Pearson Types II and VII elliptically contoured distributions, Khintchine distributions, and the unifying class for the Burr, Pareto, and logistic distributions. Extensively illustrated--the figures are unique, attractive, and reveal very nicely what distributions ``look like.'' Contains an extensive and up-to-date bibliography culled from journals in statistics, operations research, mathematics, and computer science.




Methods and Applications of Statistics in Business, Finance, and Management Science


Book Description

Inspired by the Encyclopedia of Statistical Sciences, Second Edition, this volume presents the tools and techniques that are essential for carrying out best practices in the modern business world The collection and analysis of quantitative data drives some of the most important conclusions that are drawn in today's business world, such as the preferences of a customer base, the quality of manufactured products, the marketing of products, and the availability of financial resources. As a result, it is essential for individuals working in this environment to have the knowledge and skills to interpret and use statistical techniques in various scenarios. Addressing this need, Methods and Applications of Statistics in Business, Finance, and Management Science serves as a single, one-of-a-kind resource that guides readers through the use of common statistical practices by presenting real-world applications from the fields of business, economics, finance, operations research, and management science. Uniting established literature with the latest research, this volume features classic articles from the acclaimed Encyclopedia of Statistical Sciences, Second Edition along with brand-new contributions written by today's leading academics and practitioners. The result is a compilation that explores classic methodology and new topics, including: Analytical methods for risk management Statistical modeling for online auctions Ranking and selection in mutual funds Uses of Black-Scholes formula in finance Data mining in prediction markets From auditing and marketing to stock market price indices and banking, the presented literature sheds light on the use of quantitative methods in research relating to common financial applications. In addition, the book supplies insight on common uses of statistical techniques such as Bayesian methods, optimization, simulation, forecasting, mathematical modeling, financial time series, and data mining in modern research. Providing a blend of traditional methodology and the latest research, Methods and Applications of Statistics in Business, Finance, and Management Science is an excellent reference for researchers, managers, consultants, and students in the fields of business, management science, operations research, supply chain management, mathematical finance, and economics who must understand statistical literature and carry out quantitative practices to make smart business decisions in their everyday work.




Knapsack Problems


Book Description

Thirteen years have passed since the seminal book on knapsack problems by Martello and Toth appeared. On this occasion a former colleague exclaimed back in 1990: "How can you write 250 pages on the knapsack problem?" Indeed, the definition of the knapsack problem is easily understood even by a non-expert who will not suspect the presence of challenging research topics in this area at the first glance. However, in the last decade a large number of research publications contributed new results for the knapsack problem in all areas of interest such as exact algorithms, heuristics and approximation schemes. Moreover, the extension of the knapsack problem to higher dimensions both in the number of constraints and in the num ber of knapsacks, as well as the modification of the problem structure concerning the available item set and the objective function, leads to a number of interesting variations of practical relevance which were the subject of intensive research during the last few years. Hence, two years ago the idea arose to produce a new monograph covering not only the most recent developments of the standard knapsack problem, but also giving a comprehensive treatment of the whole knapsack family including the siblings such as the subset sum problem and the bounded and unbounded knapsack problem, and also more distant relatives such as multidimensional, multiple, multiple-choice and quadratic knapsack problems in dedicated chapters.




Cryptographic Applications of Analytic Number Theory


Book Description

The book introduces new techniques that imply rigorous lower bounds on the com plexity of some number-theoretic and cryptographic problems. It also establishes certain attractive pseudorandom properties of various cryptographic primitives. These methods and techniques are based on bounds of character sums and num bers of solutions of some polynomial equations over finite fields and residue rings. Other number theoretic techniques such as sieve methods and lattice reduction algorithms are used as well. The book also contains a number of open problems and proposals for further research. The emphasis is on obtaining unconditional rigorously proved statements. The bright side of this approach is that the results do not depend on any assumptions or conjectures. On the downside, the results are much weaker than those which are widely believed to be true. We obtain several lower bounds, exponential in terms of logp, on the degrees and orders of o polynomials; o algebraic functions; o Boolean functions; o linear recurrence sequences; coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as small as pI/2+O:). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.