Probability theory and combinatorial optimization. (English) Zbl 0916.90233

Steele, J. Michael

CBMS-NSF Regional Conference Series in Applied Mathematics. 69. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. viii, 159 p. (1997).

The author treats combinatorial optimization using probability theory. Several subjects are treated with unified methods. In the first chapter statements are proved on the longest common subsequence of two sequences consisting of letters of a finite alphabet. The alphabet of four letters is the basis of the DNA analysis; a long common subsequence indicates that the two organisms originate from a common ancestor. The second subject of the first chapter is the probabilistic refinement of a theorem of P. Erdős and G. Szekeres [Compositio Math. 2, 463-470 (1935; Zbl 0012.27010)], stating that in a sequence of \(nm+1\) distinct real numbers one can find either an increasing subsequence of \(n+1\) elements, or else a decreasing subsequence of \(m+1\) elements. A proof of this result, due to J. M. Hammersley [Ann. Appl. Probab. Supplement, 47-68 (1972; Zbl 0248.60080)] is reproduced. The “probabilistic” question here is the expectancy of the length of the longest increasing (or decreasing) subsequence. The method of attacking these problems is the notion of subadditivity and an inequality of Azuma, which is related to S. Bernstein’s improvement of the classical Chebyshev inequality. In the later chapters more, more complicated, but similar problems are treated, for instance the problem of the traveling salesman and that of assigning \(n\) jobs to \(n\) machines in the most economic way. For the complicated details one has to refer to the book.

Reviewer: P.Szüsz (Glen)

MSC:

90C27	Combinatorial optimization
90C35	Programming involving graphs or networks
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
92D20	Protein sequences, DNA sequences

Keywords:

subadditivity; traveling salesman

Citations:

Zbl 0012.27010; Zbl 0248.60080