Abstract
Randomized approximation algorithms for counting problems have been the subject of many papers and monographs in theoretical computer science (see [13, 15, 25, 26]). At the same time, rare event simulation methodology has a long history of development within the applied probability and operations research communities. In this chapter, we offer a primer on the subject of approximate counting using rare event simulation techniques, thereby connecting two distinct points of view. The use of rare event simulation techniques for counting is very recent (see [5, 22]) and we hope that this chapter will motivate researchers in the rare event simulation community to consider the types of problems that we will discuss. Our focus, consequently, is on the theoretical properties of randomized approximation algorithms for counting and their connections to rare event simulation. Even though powerful heuristic algorithms …
Authors
José Blanchet, Daniel Rudoy
Publication date
2009/3/20
Journal
Rare Event Simulation Using Monte Carlo Methods
Pages
171-192
Publisher
John Wiley & Sons, Ltd
