Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers

Shuji Kijima () and Tomomi Matsui

Annals of Operations Research, 2008, vol. 162, issue 1, 35-55

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. Copyright Springer Science+Business Media, LLC 2008

Keywords: Markov chain Monte Carlo; Fully polynomial-time randomized approximation scheme; Perfect simulation; Queueing network; Product form solution (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-008-0317-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:162:y:2008:i:1:p:35-55:10.1007/s10479-008-0317-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-008-0317-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().