National Academies Press: OpenBook

Probability and Algorithms (1992)

Chapter: Front Matter

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
This page in the original is blank.
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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.

Page viii Cite
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
This page in the original is blank.
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×

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

Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
This page in the original is blank.
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R1
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R2
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R3
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R4
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R5
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R6
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R7
Page viii Cite
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R8
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R9
Suggested Citation:"Front Matter." National Research Council. 1992. Probability and Algorithms. Washington, DC: The National Academies Press. doi: 10.17226/2026.
×
Page R10
Next: 1 Introduction »
Probability and Algorithms Get This Book
×
Buy Paperback | $50.00
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

Some of the hardest computational problems have been successfully attacked through the use of probabilistic algorithms, which have an element of randomness to them. Concepts from the field of probability are also increasingly useful in analyzing the performance of algorithms, broadening our understanding beyond that provided by the worst-case or average-case analyses.

This book surveys both of these emerging areas on the interface of the mathematical sciences and computer science. It is designed to attract new researchers to this area and provide them with enough background to begin explorations of their own.

  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook, NAP.edu's online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    Switch between the Original Pages, where you can read the report as it appeared in print, and Text Pages for the web version, where you can highlight and search the text.

    « Back Next »
  6. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  7. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  8. ×

    View our suggested citation for this chapter.

    « Back Next »
  9. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!