Finding the best assignment of people to tasks or designing a highway system or communications network for maximum throughput are examples of the kind of problem that this textbook examines--the general network optimization problem with linear cost. This is the sole category of problem discussed in the book. The subcategories (for example, assignment, maximum flow, or transportation problems) can be analyzed formally using similar mathematical constructs, however, and practical solutions can be found using the same general algorithmic approaches.

Bertsekas discusses three classes of algorithms. Simplex methods compose the first group. They are included because of their historical importance and for the sake of completeness. The other two approaches--dual ascent (relaxation) and auction methods--have been closely associated with the author and are emphasized in the text.

The book has four long chapters of text and exercises in which the problem area is discussed, definitions and theorems are presented, and algorithms are analyzed. A short fifth chapter contains data on the performance of the algorithms on a Macintosh computer. FORTRAN listings of most of the algorithms in the text are given in a long appendix. At the very end of the book is a lengthy list of recent references.

The first chapter is an overview of the text. It recounts examples of the types of problems to be studied, states definitions, proves fundamental theorems, and describes algorithms. The three algorithmic approaches are introduced in this chapter for further detailed discussion in the subsequent chapters. From the beginning, Bertsekas uses a formal and mathematical presentation that continues throughout the book. He discusses the example problems at a high level of abstraction. Real-world case studies are absent.

Each of the three groups of algorithms receives its own chapter, in which the introductory presentation of the algorithms is more fully developed. The second chapter discusses simplex methods using spanning trees. This approach may be unfamiliar to the reader who is accustomed to thinking of simplex optimization of n variables as the amoeba-like movement of a geometric figure with n+1 vertices in an n-dimensional space. The physical model is empirical, and it is probably familiar to many scientists and engineers who apply simplex methods. The textbook takes a rigorous approach that complements the empirical, physical model. Simplex programs are not included among the FORTRAN listings. Since the chapter emphasizes formal analysis, this omission is not too surprising.

The third chapter, on dual ascent methods, is the shortest of the four major chapters. Likewise, a major program that implements relaxation is not included among the source code listings. Although this program can be obtained from the author, it would have been preferable to have the source code for study with the book. One can learn a lot from studying the implementation in code when the formal presentation of the algorithm may seem obscure.

The fourth chapter is on auction methods. This chapter is nearly as long as the first chapter and more completely supplemented by the programs in the listings at the end of the textbook. This chapter most thoroughly integrates the problems and fundamental material from the first chapter. It seems clear that the author intended to demonstrate the more general usefulness of auction methods compared with the simplex and relaxation methods.

Although the chapters are long, each is broken into sections that concentrate on more specific issues, and each section has its own set of exercises for the student. The exercises are mostly demonstrations and proof-oriented problems. The student will need a good background in the formal methods of mathematics or the more theoretical parts of computer science (in contrast to computational mathematics or scientific computation). At the end of each chapter is a section of notes in which the author gives his perspective on how each of the previous sections of the chapter relates to the research literature. This section is a good critical guide for further inquiry into the references given in the last appendix. The chapter number is left out of the numbering system for exercises and equations. The numbering system is consistent within the chapters, using the section number as the major field for identifying these items, but references spanning chapters require circumlocutions.

Ninety pages of program listings in FORTRAN illustrate most of the algorithms in chapters 1, 3, and 4. The first program generates sample problem data for computational analysis by the remaining programs. All of the programs in the book plus three programs not listed (an all-destinations labeling program using a binary heap, the relaxation program, and an &egr;-relaxation with negative surplus program) can be purchased from the author for an additional $25 in Macintosh and MS-DOS versions. On the one hand, I appreciate the inclusion of so much source code. On the other hand, the reader may wonder how many more pages would have been necessary to be complete. Even if all the programs had been listed in the text, however, the $25 charge for the diskette would be money well spent.

The textbook, plus the extra diskette, would be a complete learning package for either a graduate student or a professional studying on his or her own. The textbook provides the rigor, and the listings provide the practical implementation. It is a solid combination.