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

DOI10.1007/BF01190899MaRDI QIDQ1209735zbMATH OpenOpenAlexFDO

Authors E. 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

two-dimensional packingbin-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)

Recommendations

• Probabilistic analysis of shelf algorithms for strip packing
• Probabilistic analysis of a new class of strip packing algorithms
• On Two Dimensional Packing
• Two-dimensional rectangle packing: On-line methods and results
• On-line algorithms for packing rectangles into several strips

Cites work

• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3421754 (Why is no real title available?)
• A provably efficient algorithm for dynamic storage allocation
• A stochastic model of bin-packing
• Algorithms for Packing Squares: A Probabilistic Analysis
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Average-case analysis of the modified harmonic algorithm
• Dynamic Bin Packing
• Expected performance of the shelf heuristic for 2-dimensional packing
• First-fit allocation of queues: Tight probabilistic bounds on wasted space
• Next-fit bin packing with random piece sizes
• On-line bin packing in linear time
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Probability Inequalities for Sums of Bounded Random Variables
• Shelf Algorithms for Two-Dimensional Packing Problems
• 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
• Two-dimensional packing: expected performance of simple level algorithms

Cited in

(22)

• Algorithms for Packing Squares: A Probabilistic Analysis
• Denser packings obtained in \(O(n \log \log n)\) time
• scientific article; zbMATH DE number 1512697 (Why is no real title available?)
• Precise asymptotics for a random walker’s maximum
• Two-dimensional packing algorithms for layout of disconnected graphs
• A simulated annealing approach to the nesting problem in the textile manufacturing industry
• Unified solution of the expected maximum of a discrete time random walk and the discrete flux to a spherical trap
• Two-dimensional rectangle packing: On-line methods and results
• Probabilistic analysis of a new class of strip packing algorithms
• First gap statistics of long random walks with bounded jumps
• Average-case analysis of cutting and packing in two dimensions
• Recent advances on two-dimensional bin packing problems
• The nesting problem in the leather manufacturing industry
• Expected performance of the shelf heuristic for 2-dimensional packing
• Average-case performance analysis of a 2D strip packing algorithm -- NFDH
• On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis
• The Maximum of a Random Walk and Its Application to Rectangle Packing
• Expected maximum of bridge random walks & Lévy flights
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• On some packing problem related to dynamic storage allocation
• Universal first-passage properties of discrete-time random walks and Lévy flights on a line: statistics of the global maximum and records
• Probabilistic analysis of shelf algorithms for strip packing

This page was built for publication: Packings in two dimensions: Asymptotic average-case analysis of algorithms

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