Probabilistic analysis of packing and partitioning algorithms.

*(English)*Zbl 0759.90043
Wiley-Interscience Series in Discrete Mathematics and Optimization. New York, NY etc.: John Wiley & Sons, Inc. XIV, 192 p. (1991).

There are several ways of coping with hard problems of combinatorial optimization. One important possibility is to use efficient algorithms that produce good approximate solutions for most instances. Obviously a mathematical analysis of such algorithms requires application of probability theory. Typically the expected behaviour of approximation algorithms under particular probability distributions on the problem instances is studied.

The book is concerned with a wide variety of techniques for the probabilistic analysis of algorithms for problems that require the partitioning of a finite family of nonnegative members so that the sums of the numbers in the members of the partition have a given property. Typical examples are the makespan minimization in a multiprocessor system and one-dimensional bin-packing problems. However most of the presented techniques can be useful also in other areas of combinatorial optimization.

The first chapter lays down notational conventions and discusses illustrative examples and several algorithms for makespan scheduling and bin packing. The background results from probability theory and the basic approaches to the probabilistic analysis of algorithms are presented in the second chapter.

The third chapter focusses on the results for the stochastic planar matching problems. The techniques and results of Chapters 2 and 3 are then applied to the analysis of algorithms for the makespan scheduling and partitioning problems (Chapter 4), and to the analysis of one- dimensional bin packing (Chapters 5 and 6). Chapter 7, which concludes the book, is devoted to algorithms for packing problems in two dimensions.

The reader is assumed to have some prior knowledge of probability theory, expecially of classical inequalities and limit laws.

The book is concerned with a wide variety of techniques for the probabilistic analysis of algorithms for problems that require the partitioning of a finite family of nonnegative members so that the sums of the numbers in the members of the partition have a given property. Typical examples are the makespan minimization in a multiprocessor system and one-dimensional bin-packing problems. However most of the presented techniques can be useful also in other areas of combinatorial optimization.

The first chapter lays down notational conventions and discusses illustrative examples and several algorithms for makespan scheduling and bin packing. The background results from probability theory and the basic approaches to the probabilistic analysis of algorithms are presented in the second chapter.

The third chapter focusses on the results for the stochastic planar matching problems. The techniques and results of Chapters 2 and 3 are then applied to the analysis of algorithms for the makespan scheduling and partitioning problems (Chapter 4), and to the analysis of one- dimensional bin packing (Chapters 5 and 6). Chapter 7, which concludes the book, is devoted to algorithms for packing problems in two dimensions.

The reader is assumed to have some prior knowledge of probability theory, expecially of classical inequalities and limit laws.

Reviewer: M.Vlach (Praha)

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C27 | Combinatorial optimization |

68Q25 | Analysis of algorithms and problem complexity |

60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |