Towards a Polynomial-Time Randomized Algorithm for Closed Product-Form Networks

Wu-Lin Chen and Colm O'Cinneide

Industrial Engineering
Schools of Engineering
Purdue University
West lafayette, Indiana

chenwl@ecn.purdue.edu

colm@ecn.purdue.edu

http://palette.ecn.purdue.edu/~chenwl/

http://palette.ecn.purdue.edu/~colm/

ACM Transactions on Modeling and Computer Simulation
vol. 8, no. 3 (July 1998)

Paper (PostScript 265 KB)
Paper (GZipped PostScript 84 KB)
Papers only available to TOMACS subscribers and others authorized to access the ACM Digital Library.

Abstract

We present a Markov chain Monte Carlo method for class throughputsin closed multiclass product-form networks. The method is as follows. For a given network, we construct a ``regularized'' network with a highly simplified structure that has the same steady-state distribution.We then simulate the regularized network. The method has performed reasonably well across a broad range of problems. We give a heuristic explanation of this. We prove that the regularized network ``mixes in polynomial time'' in some special cases.

General Terms

Algorithms

Categories and Subject Descriptors

G.3[Mathematics of Computing]: Probability and Statistics
I.6.8[Simulation and Modeling]: Types of Simulation-Monte Carlo

Additional Keywords and Phrases

Simulation, Markov Chain Monte Carlo, Closed Product-Form Multi-class Networks, Rapid Mixing