NOTICE: The project that is the subject of this report was approved by the Governing Board of the National Research Council, whose members are drawn from the councils of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine. The members of the committee responsible for the report were chosen for their special competences and with regard for appropriate balance.
This report has been reviewed by a group other than the authors according to procedures approved by a Report Review Committee consisting of members of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine.
The National Academy of Sciences is a private, nonprofit, self-perpetuating society of distinguished scholars engaged in scientific and engineering research, dedicated to the furtherance of science and technology and to their use for the general welfare. Upon the authority of the charter granted to it by the Congress in 1863, the Academy has a mandate that requires it to advise the federal government on scientific and technical matters. Dr. Frank Press is president of the National Academy of Sciences.
The National Academy of Engineering was established in 1964, under the charter of the National Academy of Sciences, as a parallel organization of outstanding engineers. It is autonomous in its administration and in the selection of its members, sharing with the National Academy of Sciences the responsibility for advising the federal government. The National Academy of Engineering also sponsors engineering programs aimed at meeting national needs, encourages education and research, and recognizes the superior achievements of engineers. Dr. Robert M. White is president of the National Academy of Engineering.
The Institute of Medicine was established in 1970 by the National Academy of Sciences to secure the services of eminent members of appropriate professions in the examination of policy matters pertaining to the health of the public. The Institute acts under the responsibility given to the National Academy of Sciences by its congressional charter to be an adviser to the federal government and, upon its own initiative, to identify issues of medical care, research, and education. Dr. Kenneth I. Shine is president of the Institute of Medicine.
The National Research Council was organized by the National Academy of Sciences in 1916 to associate the broad community of science and technology with the Academy’s purposes of furthering knowledge and advising the federal government. Functioning in accordance with general policies determined by the Academy, the Council has become the principal operating agency of both the National Academy of Sciences and the National Academy of Engineering in providing services to the government, the public, and the scientific and engineering communities. The Council is administered jointly by both Academies and the Institute of Medicine. Dr. Frank Press and Dr. Robert M. White are chairman and vice chairman, respectively, of the National Research Council.
The National Research Council established the Board on Mathematical Sciences in 1984. The objectives of the board are to maintain awareness and active concern for the health of the mathematical sciences and to serve as the focal point in the National Research Council for issues connected with the mathematical sciences. The board conducts studies for federal agencies and others and maintains liaison with the mathematical sciences communities, academia, professional societies, and industry.
Support for this project was provided by the Air Force Office of Scientific Research, the Army Research Office, and the National Science Foundation.
Library of Congress Catalog Card No. 92-60700
International Standard Book Number 0-309-04776-5
Additional copies of this report are available from:
National Academy Press
2101 Constitution Avenue, NW Washington, DC 20418
S-612
Printed in the United States of America
PANEL ON PROBABILITY AND ALOGRITHMS
J. MICHAEL STEELE,
University of Pennsylvania,
Chair
DAVID ALDOUS,
University of California at Berkeley
DIMITRIS J. BERTSIMAS,
Massachusetts Institute of Technology
EDWARD G. COFFMAN,
AT&T Bell Laboratories
DORIT HOCHBAUM,
University of California at Berkeley
MICHA HOFRI,
University of Houston
JEFFREY C. LAGARIAS,
AT&T Bell Laboratories
SCOTT T. WEIDMAN, Senior Staff Officer
COMMITTEE ON APPLIED AND THEORETICAL STATISTICS
WILLIAM F. EDDY,
Carnegie Mellon University,
Chair
YVONNE BISHOP,
U.S. Department of Energy
DONALD P. GAVER,
Naval Postgraduate School
PREM K. GOEL,
Ohio State University
DOUGLAS M. HAWKINS,
University of Minnesota
DAVID G. HOEL,
National Institute of Environmental Health Sciences
JON KETTENRING,
Bellcore
CARL N. MORRIS,
Harvard University
KARL E. PEACE, Biopharmaceutical Research Consultants
JAYARAM SETHURAMAN,
Florida State University
JOHN R. TUCKER, Staff Officer
BOARD ON MATHEMATICAL SCIENCES
SHMUEL WINOGRAD,
IBM T.J. Watson Research Center,
Chair
RONALD DOUGLAS,
State University of New York-Stony Brook,
Vice-Chair
LAWRENCE D. BROWN,
Cornell University
SUN-YUNG A. CHANG,
University of California at Los Angeles
JOEL E. COHEN,
Rockefeller University
AVNER FRIEDMAN,
University of Minnesota
JOHN F. GEWEKE,
University of Minnesota
JAMES G. GLIMM,
State University of New York-Stony Brook
PHILLIP A. GRIFFITHS,
Institute for Advanced Study
DIANE LAMBERT,
AT&T Bell Laboratories
GERALD J. LIEBERMAN,
Stanford University
RONALD F. PEIERLS,
Brookhaven National Laboratory
JEROME SACKS,
National Institute of Statistical Sciences
Ex Officio Member
WILLIAM F. EDDY, Carnegie Mellon University Chair,
Committee on Applied and Theoretical Statistics
Staff
JOHN E. LAVERY, Director
RUTH E. O'BRIEN, Staff Associate
HANS OSER, Staff Officer
JOHN R. TUCKER, Staff Officer
SCOTT T. WEIDMAN, Senior Staff Officer
BARBARA WRIGHT, Administrative Assistant
COMMISSION ON PHYSICAL SCIENCES, MATHEMATICS, AND APPLICATIONS
NORMAN HACKERMAN,
Robert A. Welch Foundation,
Chair
PETER J. BICKEL,
University of California at Berkeley
GEORGE F. CARRIER, Professor Emeritus,
Harvard University
GEORGE W. CLARK,
Massachusetts Institute of Technology
DEAN E. EASTMAN,
IBM T.J. Watson Research Center
MARYE ANNE FOX,
University of Texas-Austin
PHILLIP A. GRIFFITHS,
Institute for Advanced Study
NEAL F. LANE,
Rice University
ROBERT W. LUCKY,
AT&T Bell Laboratories
CLAIRE E. MAX,
Lawrence Livermore Laboratory
CHRISTOPHER F. MCKEE,
University of California at Berkeley
JAMES W. MITCHELL,
AT&T Bell Laboratories
RICHARD S. NICHOLSON,
American Association for the Advancement of Science
ALAN SCHRIESHEIM,
Argonne National Laboratory
KENNETH G. WILSON,
Ohio State University
NORMAN METZGER, Executive Director
Preface
The Panel on Probability and Algorithms was constituted by the National Research Council in 1991 and charged with writing a report surveying both the topic of probabilistic algorithms, where randomization is a part of the internal calculation, and the probabilistic analysis of algorithms, in which one uses a probability model to deepen the understanding of how an algorithm functions in practice. Probabilistic algorithms—simulated annealing is one example—incorporate randomness into the underlying logic. For problems with huge solution spaces, or those where deterministic models of the processes involved do not exist, such algorithms have been very exciting developments. Probabilistic algorithms can solve certain problems faster than is possible by any deterministic algorithm. The probabilistic analysis of algorithms is a refinement of worst-case analysis, which is often too pessimistic compared to the performance of algorithms in actual practice.
Both uses of probability show tremendous promise, yet the research opportunities outnumber the people available to explore them. The panel hopes that more researchers, especially young researchers, will be intrigued by the possibilities and attracted to this field.
The panel gratefully acknowledges the substantial contributions of its contributing authors, Joan Feigenbaum, David Johnson, George Lueker, Bruce Maggs, Vijaya Rarnachandran, Ron Shamir, Peter Shor, and John Tsitsiklis. These colleagues greatly strengthened the report with their expertise. The contributions of Hans Oser, who served for a time as the project staff officer, are also appreciated.
Contents
INTRODUCTION |
||||
SIMULATED ANNEALING |
||||
APPROXIMATE COUNTING VIA MARKOV CHAINS |
||||
PROBABILISTIC ALGORITHMS FOR SPEEDUP |
||||
PROBABILISTIC ALGORITHMS FOR DEFEATING ADVERSARIES |
||||
PSEUDORANDOM NUMBERS |
||||
PROBABILISTIC ANALYSIS OF PACKING AND RELATED PARTITIONING PROBLEMS |
||||
PROBABILITY AND PROBLEMS IN EUCLIDEAN COMBINATORIAL OPTIMIZATION |
||||
RANDOMIZATION IN PARALLEL ALGORITHMS |
||||
RANDOMLY WIRED MULTISTAGE NETWORKS |
||||
MISSING PIECES, DERANDOMIZATION, AND CONCLUDING REMARKS |