PROBABILITY AND ALGORITHMS

Panel on Probability and Algorithms

Committee on Applied and Theoretical Statistics

Board on Mathematical Sciences

Commission on Physical Sciences, Mathematics, and Applications

National Research Council

National Academy Press
Washington, D.C.
1992



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page R1
Probability and Algorithms PROBABILITY AND ALGORITHMS Panel on Probability and Algorithms Committee on Applied and Theoretical Statistics Board on Mathematical Sciences Commission on Physical Sciences, Mathematics, and Applications National Research Council National Academy Press Washington, D.C. 1992

OCR for page R1
Probability and Algorithms 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

OCR for page R1
Probability and Algorithms 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

OCR for page R1
Probability and Algorithms 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

OCR for page R1
Probability and Algorithms 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

OCR for page R1
Probability and Algorithms This page in the original is blank.

OCR for page R1
Probability and Algorithms 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.

OCR for page R1
Probability and Algorithms This page in the original is blank.

OCR for page R1
Probability and Algorithms Contents 1.   INTRODUCTION J. Michael Steele and David Aldous   1 2.   SIMULATED ANNEALING Dimitris Bertsimas and John Tsitsiklis   17 3.   APPROXIMATE COUNTING VIA MARKOV CHAINS David Aldous   31 4.   PROBABILISTIC ALGORITHMS FOR SPEEDUP Joan Feigenbaum and Jeffrey C. Lagaria   39 5.   PROBABILISTIC ALGORITHMS FOR DEFEATING ADVERSARIES Joan Feigenbaum   53 6.   PSEUDORANDOM NUMBERS Jeffrey C. Lagarias   65 7.   PROBABILISTIC ANALYSIS OF PACKING AND RELATED PARTITIONING PROBLEMS G. Coffman, Jr., D.S. Johnson, P.W. Shor, and G.S. Lueker   87 8.   PROBABILITY AND PROBLEMS IN EUCLIDEAN COMBINATORIAL OPTIMIZATION J. Michael Steele   109 9.   PROBABILISTIC ANALYSIS IN LINEAR PROGRAMMING Ron Shamir   131 10.   RANDOMIZATION IN PARALLEL ALGORITHMS Vijaya Ramachandran   149 11.   RANDOMLY WIRED MULTISTAGE NETWORKS Bruce M. Maggs   161 12.   MISSING PIECES, DERANDOMIZATION, AND CONCLUDING REMARKS J. Michael Steele   175

OCR for page R1
Probability and Algorithms This page in the original is blank.