In this paper, we propose a fully polynomial-time randomized approximation scheme for computing the expectation of the critical path length in a stochastic directed acyclic network. Our algorithm is based on the Markov chain Monte Carlo method, and our scheme returns an approximate solution, for which the size of error satisfies a given error rate. We propose a Markov chain and a perfect sampling algorithm based on coupling from the past method.
各種検索
サポート
ヘルプ