A provably efficient algorithm for dynamic storage allocation

DOI10.1016/0022-0000(89)90031-7zbMath0723.60117OpenAlexW4230764056MaRDI QIDQ756873

Frank Thompson Leighton, Edward G. jun. Coffman

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90031-7

zbMATH Keywords

Poisson processexperimental databin-packingdesign and analysis of algorithms for on-line dynamic storage allocationplanar matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Related Items

Asymptotic expansions for a stochastic model of queue storage, Some Exact and Asymptotic Solutions to Single Server Models of Dynamic Storage, The distribution of wasted spaces in the M/M/∞ queue with ranked servers, The online graph bandwidth problem, An efficient deterministic heuristic for two-dimensional rectangular packing, Packings in two dimensions: Asymptotic average-case analysis of algorithms, Storage allocation under processor sharing. I: Exact solutions and asymptotics, Fuzzy bin packing problem., Average-case analysis of cutting and packing in two dimensions, Stochastic on-line knapsack problems, Storage allocation under processor sharing II: Further asymptotic results, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, First-fit allocation of queues: Tight probabilistic bounds on wasted space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The M/M/\(\infty\) service system with ranked servers in heavy traffic. With a preface by Franz Ferschl
• Some interesting processes arising as heavy traffic limits in an M/M/\(\infty\) storage process
• The average-case analysis of some on-line algorithms for bin packing
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Weak convergence of compound stochastic process. I
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• Algorithms for resolving conflicts in dynamic storage allocation
• On the external storage fragmentation produced by first-fit and best-fit allocation strategies
• Limiting diffusion approximations for the many server queue and the repairman problem
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations