Packings in two dimensions: Asymptotic average-case analysis of algorithms

DOI10.1007/BF01190899zbMath0787.68046OpenAlexW2022197039MaRDI QIDQ1209735

Edward G. jun. Coffman, Peter W. Shor

Publication date: 16 May 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01190899

zbMATH Keywords

bin-packingtwo-dimensional packingcutting stock problemsoff-line algorithmasymptotic average-case analysisdynamic packingon-line shelf packings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of packing and covering (05B40)

Related Items

A simulated annealing approach to the nesting problem in the textile manufacturing industry, The nesting problem in the leather manufacturing industry, Universal first-passage properties of discrete-time random walks and Lévy flights on a line: statistics of the global maximum and records, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, Expected maximum of bridge random walks & Lévy flights, Recent advances on two-dimensional bin packing problems, Unified solution of the expected maximum of a discrete time random walk and the discrete flux to a spherical trap, Average-case performance analysis of a 2D strip packing algorithm -- NFDH, The Maximum of a Random Walk and Its Application to Rectangle Packing, Precise asymptotics for a random walker’s maximum, Two-dimensional packing algorithms for layout of disconnected graphs, First gap statistics of long random walks with bounded jumps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit allocation of queues: Tight probabilistic bounds on wasted space
• A provably efficient algorithm for dynamic storage allocation
• The average-case analysis of some on-line algorithms for bin packing
• Expected performance of the shelf heuristic for 2-dimensional packing
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Average-case analysis of the modified harmonic algorithm
• Dynamic Bin Packing
• Shelf Algorithms for Two-Dimensional Packing Problems
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Algorithms for Packing Squares: A Probabilistic Analysis
• Two-dimensional packing: expected performance of simple level algorithms
• A stochastic model of bin-packing
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Next-fit bin packing with random piece sizes
• On-line bin packing in linear time
• Probability Inequalities for Sums of Bounded Random Variables