Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers |
| |
Authors: | Shuji Kijima Tomomi Matsui |
| |
Affiliation: | (1) Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan;(2) Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, Chuo, Japan |
| |
Abstract: | In this paper, we propose a fully polynomial-time randomized approximation scheme (FPRAS) for a closed Jackson network. Our algorithm is based on the Markov chain Monte Carlo (MCMC) method. Thus our scheme returns an approximate solution, for which the size of the error satisfies a given bound. To our knowledge, this algorithm is the first polynomial time MCMC algorithm for closed Jackson networks with multiple servers. We propose two new ergodic Markov chains, both of which have a unique stationary distribution that is the product form solution for closed Jackson networks. One of them is for an approximate sampler, and we show that it mixes rapidly. The other is for a perfect sampler based on the monotone coupling from the past (CFTP) algorithm proposed by Propp and Wilson, and we show that it has a monotone update function. |
| |
Keywords: | Markov chain Monte Carlo Fully polynomial-time randomized approximation scheme Perfect simulation Queueing network Product form solution |
本文献已被 SpringerLink 等数据库收录! |
|