DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 2011-02-28
著者
-
Matsui Tomomi
University of Tokyo
-
Matsui Tomomi
Faculty Of Science And Engineering Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
-
Matsui Tomomi
Univ. Of Tokyo
-
Matsui Tomomi
The Authors Are With The Department Of Mathematical Informatics Graduate School Of Information Scien
-
Matsui Tomomi
Department Of Information And System Engineering Faculty Of Science And Engineering Chuo University
-
Yamaguchi Daisuke
Department Of Information And System Engineering Faculty Of Science And Engineering Chuo University
-
Yamaguchi Daisuke
Department Of Biochemistry And Molecular Biology Faculty Of Science Saitama University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
関連論文
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- An Optimal Grey PID Control System
- Size Distribution and Characteristics of Chemical Components in Ambient Particulate Matter
- Improved Approximation Algorithms for Firefighter Problem on Trees
- Phase Separated Structures in a Binary Blend of Diblock Copolymers under an Extensional Force Field : Helical Domain Structure (Cross-disciplinary Physics and Related Areas of Science and Technology)
- Detection of Weak Sugar Binding Activity of VIP36 using VIP36-streptavidin Complex and Membrane-based Sugar Chains
- Successful Manipulation in Stable Marriage Model with Complete Preference Lists
- 2-C-14 Cheating Strategies for Gale-Shapley Algorithm with Complete Preference Lists
- A note on Asymmetric Power Index for Voting Games
- A note on mixed level supersaturated designs
- Approximate Counting Scheme for m×n Contingency Tables(Foundations of Computer Science)
- Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(Discrete Mathematics and Its Applications)
- Home-Away Table Feasibility Problem
- Notes on Equitable Round-Robin Tournaments(Special Section on Discrete Mathematics and Its Applications)
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
- Linear Relaxation for Hub Network Design Problems
- DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
- Oral habits of temporomandibular disorder patients with malocclusion
- Properties and Physiological Functions of UDP-Sugar Pyrophosphorylase in Arabidopsis
- 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization
- Differential activation of mitogen-activated protein kinases and glial cells in the trigeminal sensory nuclear complex following lingual nerve injury
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Note on Equitable Round-Robin Tournaments
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- Observation of a Discontinuity in the Value of I_m^- at the Order-Disorder Transition in Diblock Copolymer/Homopolymer and Diblock Copolymer/Diblock Copolymer Blends
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)
- Dengue Hemorrhagic Shock and Disseminated Candidiasis
- 3C2 INVERSE ASSIGNMENT PROBLEM FOR TIMETABLING IN TUTORING SCHOOL(Technical session 3C: OS2: Timetabling and assignment problems(2))
- Radiographic Progression of Silicosis among Japanese Tunnel Workers in Kochi