Hu T.C. - Combinatorial algorithms

This book presents some combinatorial algorithms common in computer science and operations research. The presentation is to stress intuitive ideas in an algorithm and to illustrate it with a numerical example. The detailed implementation of the algorithms in PASCAL are in a separate manual. No background in linear programming and advanced data structure is needed. Most of the material can be taught to undergraduates while more difficult sections are only suitable to graduate students. Chapters can be read somewhat independently so that the instructor can select a subset of chapters for his course. This book should also be useful as a reference book since it contains much material not available in Journals or any other books.

Chapters One and Two can be used in a one quarter course in network theory or graph algorithms. Chapter One goes in-depth into several shortest-path problems and introduces a decomposition algorithm for large sparse networks. Chapter Two deals with network flows, and contains a large amount of new material, such as the algorithms of Dinic and Kazanov which have never appeared in English before, the optimum communication spanning tree and the description of PERT in terms of longest paths and cheapest cuts. Also in Chapter Two is a section on multi-terminal flows where a subset of nodes are terminal nodes.

Chapters Three and Four cover dynamic programming and backtrack (branch and bound) which are two general optimization techniques. Both topics are usually not covered in detail in computer science departments. Chapter Three introduces the concept of dynamic programming by using examples carefully selected to show the variety of problems solvable by dynamic programming. After the knapsack problem is solved, the periodic nature of the solutions is discussed. (The solution to the two-dimensional knapsack problem is based on the papers of Gilmore and Gomory.) This chapter ends with a brief discussion of the work of Dr. F.F. Yao. Chapter Four includes standard material on backtracking as well as a detailed description of pruning in a game tree. It also gives an example of the Monte Carlo technique of estimating the size of the decision tree.

Chapters Five and Six contain a large amount of new material which should be of interest to computer scientists and operations researchers. Chapter Five introduces the Huffman algorithm, the Hu-Tucker algorithm, including a new reconstruction phase, and the generalization of both algorithms to regular cost functions. This generalization is based on the paper by Hu, Kleitman and Tamaki. Chapter Five also describes and illustrates the Garsia-Wachs construction. Chapter Six deals with heuristic algorithms. It contains the one-point theorem of Magazine, Nemhauser and Trotter and the new bin-packing algorithm of Yao. The treatment of job-scheduling for the tree-constraint is a revision of the authors paper published in 1961.

The subject of Chapter Seven is matrix multiplications. This chapter contains two combinatorial results, the Strassens result on the multiplication of two large matrices and the results on the optimum order of multiplying a chain of matrices of different dimensions. Although the problem of optimum order can be solved by an O(n3) algorithm based on dynamic programming, the problem can now be solved by an O(nlogn) algorithm based on combinatorial insights. Since the subject of finding the optimum order is a book by itself, we give the main theorems on the subject and a heuristic O(n) algorithm which has a 15% error bound.

The final chapter, Chapter Eight, introduces the concepts of NP-complete problems. The purpose here is to give the reader some intuitive notions but not a complete treatment since a book has been published dealing with this subject in detail.

It is a pleasure to thank all persons who helped to make this book possible. To the National Science Foundation and Dr. J. Chandra and Dr. P. Boggs of the U. S. Army Research Office for their financial help. To Drs. F. Chin, S. Dreyfus, F. Ruskey, W. Savitch, A. Tucker, M. Wachs, F. Yao for reading various parts of the drafts. To Professor L. E. Trotter, Jr. and Professor Andrew Yao for reading the next-to-final version of the whole book and made many valuable suggestions. To Mrs. Mary Deo for her effort in editing the earlier versions. To Mrs. Annetta Whiteman for her excellent technical typing of so many versions of the book. To Ms. Sue Sullivan, for skillfully converting the material into the book formats using the UNIX system. To Mr. Y.S. Kuo for preparing the index and writing parts of the manual. And last but most to Dr. Man-Tak Shing, for writing the manual and his technical and general assistance throughout the writing and production.

La Jolla, California

October 19, 1981

T. C. Hu