Fluid limits, bin packing, and stochastic analysis of algorithms

E. G. Coffman, A. L. Stolyar

Research output: Contribution to conferencePaper

Abstract

A fluid-limit process approximates a given stochastic process on a large scale in both time and space, providing useful asymptotics for evaluating the performance of computer and communication systems. As an illustration, a discrete-time model of bin packing that arises in multimedia communication systems, computer storage allocation and transmission along slotted communication channels is considered. The main intent is to show the power of the fluid-limit approach and its feasibility as a novel tool for the probabilistic analysis of algorithms. New performance results for classical packing algorithms come as a by-product.

Original languageEnglish (US)
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fluid limits, bin packing, and stochastic analysis of algorithms'. Together they form a unique fingerprint.

  • Cite this

    Coffman, E. G., & Stolyar, A. L. (1999). Fluid limits, bin packing, and stochastic analysis of algorithms. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .