Randomized algorithms: Approximation, generation and counting

Publication date 19 February 2001

Published in Distinguished Dissertations (Search for Journal in Brave)

approximative counting approximative sampling path coupling sampling

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Randomized algorithms (68W20)

Review text

This dissertation concerns primarily with approximative solutions of two problems: given a finite set of combinatorial objects, determine how many objects there are in it and pick one uniformly at random. Both of these problems -- counting and generation (or sampling) -- are often difficult to solve exactly as they are intractable by computational complexity theory. Chapter 1 reviews the mathematical background within which the research in this book is set. Some less well-known computational complexity classes are described, Markov processes as well as some definitions from graph theory are briefly introduced. In Chapter 2 ``Techniques for Sampling and Approximative Sampling the author outlines some simple methods and the Markov chain method for sampling. Different ``stop criteria for simulation of corresponding Markov chains are presented with proofs (Coupling Lemma, Dobrushin's Criterion, etc.). In Chapter 3 ``Approximative Counting the principles of direct sampling, Karp-Luby technique and the Markov Chain Monte Carlo Method are well explained. New results are presented in Chapter 4 ``Application: Coupling. Result of Jerum on \(k\)-colorings of a graph is extended to hypergraphs and to the case where \(k\) is equal to twice the maximum degree of the graph. The combinatorial problems associated with graph orientations with no sink , the associated problem of Twice -- SAT, sampling a point from within a convex body and the counting variant, which is to approximate the volume of the convex body are considered. The author presents probably first analysis of such a class of Markov chains that uses the coupling methods. In the Intermezzo path coupling is introduced as a new technique for applying the coupling method. Several results are proved that make subsequent applications of path coupling much simpler. In Chapter 5 ``Applications: Path Coupling a variety of applications of the path coupling method to show rapid mixing of certain Markov chains is considered. The associated problems -- sampling from the set of sink and source free orientations of a graph, sampling from the set of totally edge cyclic orientations of a graph, several problems from statistical physics, sampling from the set of linear extensions of a partial order and graph \(k\)-coloring are \#P-complete. Several ideas and techniques that deserve further exploration and research are introduced in Chapter 6 ``Directions for Future Work. Overall, this dissertation is really distinquished by the scope as well as by presented results. It is well written presupposing a good familiarity with basic notions of probability, Markov chains, randomized algorithms and problem complexity classes. Russ Bubley has written a book that can be highly recommended namely as a useful reference work for researchers in this area.

Recommendations

Cited in

(28)

This page was built for publication: Randomized algorithms: Approximation, generation and counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2701738)