Dmitry Lifshitz

Cross-entropy Application: Combinatorial Optimization, Counting, and Rare Events Estimation Dmitry Lifshitz

Many important problems in science, engineering, and mathematics deal with counting problems that are #P-complete, like counting the number of perfect matches in a bipartite graph, determining the permanent of a matrix, counting the number of fixed-size cliques in a graph, and the number of forests in a graph. In this book we show how #P-complete counting problems can be viewed as particular instances of estimation problems, and as such can be solved efficiently via Monte Carlo techniques. We show how to resolve, at least partially, the curse of dimensionality of likelihood ratios while using importance sampling (IS) to estimate the performance of high-dimensional Monte Carlo simulation problems. The curse of dimensionality, which is better known under the name ?the degeneracy properties of likelihood ratios? is one of the central topics in Monte Carlo simulation. The material is addressed to the students, practitioners or anyone else studying Monte Carlo simulation, combinatorial optimization, or simulation-based performance analysis of stochastic systems.