O'Reilly logo

Fast Sequential Monte Carlo Methods for Counting and Optimization by Radislav Vaisman, Ad Ridder, Reuven Y. Rubinstein

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 4

Splitting Method for Counting and Optimization

4.1 Background

This chapter deals with the splitting method for counting, combinatorial optimization, and rare-event estimation. Before turning to the splitting method we present some background on counting using randomized (or Monte Carlo) algorithms.

To date, very little is known about how to construct efficient algorithms for hard counting problems. This means that exact solutions to these problems cannot be obtained in polynomial time, and therefore our work focuses on approximation algorithms, and, in particular, approximation algorithms based on randomization. The basic procedure for counting is outlined below.

1. Formulate the counting problem as estimating the cardinality c04-math-0001 of some set c04-math-0002, such as the one in (1.1).
2. Find a sequence of decreasing sets c04-math-0003 such that

4.1 c04-math-0004

and c04-math-0005 is known.

3. Write c04-math-0006 as

4.2

where

4.3

Note that is typically ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required