In this paper the authors study a problem concerning closed Jackson networks with single servers. They propose a fully polynomial-time randomized approximation scheme for calculating an approximate value of the normalizing constant in the product form solution for a Jackson network of this type. Their scheme is based on the Markov chain Monte Carlo (MCMC) method. Particularly they make use of a Markov chain which has the product form solution of a given closed Jackson network as a unique stationary distribution and show that the chain mixes in O(n2lnK), where n is the number of nodes and K is the number of customers in the closed Jackson network. Thus their scheme is a polynomial-time approximation scheme. Leonardo Pasini
Recensione dell'articolo: (Kijima, S.; Matsui, T. - "Approximation algorithm and perfect sampler for closed Jackson networks with single server" - SIAM J.Comput. 38 (2008), no.4, 1484–1503.)
PASINI, Leonardo
2010-01-01
Abstract
In this paper the authors study a problem concerning closed Jackson networks with single servers. They propose a fully polynomial-time randomized approximation scheme for calculating an approximate value of the normalizing constant in the product form solution for a Jackson network of this type. Their scheme is based on the Markov chain Monte Carlo (MCMC) method. Particularly they make use of a Markov chain which has the product form solution of a given closed Jackson network as a unique stationary distribution and show that the chain mixes in O(n2lnK), where n is the number of nodes and K is the number of customers in the closed Jackson network. Thus their scheme is a polynomial-time approximation scheme. Leonardo PasiniI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
