Fast Sequential Monte Carlo Methods for Counting and Optimization

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 of some set , such as the one in (1.1).

2. Find a sequence of decreasing sets such that

4.1

and is known.

3. Write as

4.2

where

4.3

Note that is typically ...