A provably efficient algorithm for dynamic storage allocation

DOI10.1016/0022-0000(89)90031-7MaRDI QIDQ756873zbMATH OpenOpenAlexFDO

Authors E. G. jun. Coffman, F. Thomson Leighton

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 processbin-packingexperimental datadesign 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)

Recommendations

• scientific article; zbMATH DE number 1003306
• Tight Bounds for Dynamic Storage Allocation
• Algorithms for resolving conflicts in dynamic storage allocation
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• Efficient algorithms for dynamic allocation of distributed memory

Cites work

• scientific article; zbMATH DE number 4046862 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3259552 (Why is no real title available?)
• scientific article; zbMATH DE number 3408613 (Why is no real title available?)
• scientific article; zbMATH DE number 3025566 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• Algorithms for resolving conflicts in dynamic storage allocation
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• Limiting diffusion approximations for the many server queue and the repairman problem
• On the external storage fragmentation produced by first-fit and best-fit allocation strategies
• Some interesting processes arising as heavy traffic limits in an M/M/\(\infty\) storage process
• The M/M/\(\infty\) service system with ranked servers in heavy traffic. With a preface by Franz Ferschl
• 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

Cited in

(33)

• Storage allocation under processor sharing. I: Exact solutions and asymptotics
• Finite-size scaling approach to dynamic storage allocation problem
• Algorithms for resolving conflicts in dynamic storage allocation
• Fuzzy bin packing problem.
• scientific article; zbMATH DE number 4046862 (Why is no real title available?)
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Some exact and asymptotic solutions to single server models of dynamic storage
• Storage allocation under processor sharing. II: Further asymptotic results
• Asymptotic expansions for a stochastic model of queue storage
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• Cost-oblivious storage reallocation
• Robust storage assignment in stack- and queue-based storage systems
• First-fit allocation of queues: Tight probabilistic bounds on wasted space
• Average-case analysis of cutting and packing in two dimensions
• The online graph bandwidth problem
• Stochastic on-line knapsack problems
• Space overhead bounds for dynamic memory management with partial compaction
• Insertion and Compaction Algorithms in Sequentially Allocated Storage
• scientific article; zbMATH DE number 1003306 (Why is no real title available?)
• Dynamic storage allocation with limited compaction - complexity and some practical implications
• Dynamic storage allocation with known durations
• Optimality and greed in dynamic allocation
• The distribution of wasted spaces in the M/M/∞ queue with ranked servers
• Optimal allocation of storage space
• Analysis for the end of block wasted space
• An efficient deterministic heuristic for two-dimensional rectangular packing
• Chainmail: A Model of First-fit Memory Allocation
• Stochastic analysis of dynamic processes
• scientific article; zbMATH DE number 6399332 (Why is no real title available?)
• An infinite server system with packing constraints and ranked servers
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• A performance analysis of channel fragmentation in dynamic spectrum access systems
• Analysis of space allocation in a generally fragmented linear store

This page was built for publication: A provably efficient algorithm for dynamic storage allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756873)