Home >

news Help

Publication Information


Title
Japanese:Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network 
English:Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network 
Author
Japanese: YAMAGUCHI Daisuke, 松井知己.  
English: YAMAGUCHI Daisuke, MATSUI Tomomi.  
Language English 
Journal/Book name
Japanese:電子情報通信学会総合大会講演論文集 
English: 
Volume, Number, Page Vol. 2011    No. 1    pp. S15-S16
Published date Mar. 15, 2011 
Publisher
Japanese:一般社団法人電子情報通信学会 
English: 
Conference name
Japanese:電子情報通信学会総合大会 
English: 
Conference site
Japanese: 
English: 
Abstract 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.

©2007 Institute of Science Tokyo All rights reserved.