ENGLISH

Probabilistic Methods for Algorithmic Discrete Mathematics

Book information

Publisher
Springer
Year
1998
ISBN
3540646221
LCC
QA164 .P74 1998
Open Library ID
OL374419M
Language
english
Format
DJVU
Filesize
4 MB (4313294 bytes)
Series
Algorithms and Combinatorics
Edition
1
Pages
172\172
Library
avaxhome.ws
Time added
2010-05-31 11:05:02

Description

The book gives an accessible account of modern probabilistic methods for analyzing combinatorial structures and algorithms. It will be an useful guide for graduate students and researchers. Special features included: a simple treatment of Talagrand's inequalities and their applications; an overview and many carefully worked out examples of the probabilistic analysis of combinatorial algorithms; a discussion of the ''exact simulation'' algorithm (in the context of Markov Chain Monte Carlo Methods); a general method for finding asymptotically optimal or near optimal graph colouring, showing how the probabilistic method may be fine-tuned to exploit the structure of the underlying graph; a succinct treatment of randomized algorithms and derandomization techniques.

Similar books