• Calendar

June 10, Tuesday
12:00 – 14:00

We present a new randomized algorithm for counting, rare-events simulation, uniform sampling on different regions, and approximating the solutions of quite general NP-hard combinatorial (integer) optimization problems. Similar to the existing randomized algorithms the proposed one is based on the MCMC (Gibbs) sampler equipped with importance sampler and it also uses a sequential sampling plan to decompose a ``difficult'' problem into a sequence of ``easy'' ones. The main differences between the existing and the proposed algorithm is that the latter one has a special device, called the ``cloning'' device, which makes our algorithm very fast and accurate. In particular it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model and for sampling random variables uniformly distributed on different convex bodies. We present efficient numerical results, while solving quite general integer and combinatorial optimization problems as well as counting ones, like satisfiability problem and Hamiltonian cycles. Bio: Reuven Rubinstein is a world known expert in stochastic modeling, applied probability and Monte Carlo simulation methods. He has written over 100 articles and published six books with Wiley and Springer. His citation index is in the top 5% among the scientists in OR and applied probability worldwide. Rubinstein spent most of his sabbatical years at top universities in the world including Columbia, Harvard, Michigan and Stanford University. He is a consultant to many leading firms, including IBM, Motorola and NEC. Rubinstein is the inventor of the popular score-function method in simulation analysis and the generic cross-entropy methods for combinatorial optimization and counting. For details on the cross-entropy, which includes over 100 publications, go to http://en.wikipedia.org/wiki/Cross-entropy_method.