Average-case analysis of cutting and packing in two dimensions

DOI10.1016/0377-2217(90)90349-GzbMath0689.90059OpenAlexW2027862748MaRDI QIDQ582210

Peter W. Shor, Edward G. jun. Coffman

Publication date: 1990

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(90)90349-g

zbMATH Keywords

average-case analysiscuttingtwo-dimensional packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

A hybrid heuristic algorithm for the 2D variable-sized bin packing problem, A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints, A simulated annealing approach to the nesting problem in the textile manufacturing industry, The nesting problem in the leather manufacturing industry, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, Interactive procedures in large-scale two-dimensional cutting stock problems, Triple-solution approach for the strip packing problem with two-staged patterns, An exact algorithm for general, orthogonal, two-dimensional knapsack problems, Exact algorithms for the guillotine strip cutting/packing problem., Packing, covering and tiling in two-dimensional spaces, Packing problems, A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, Fuzzy bin packing problem., Average-case performance analysis of a 2D strip packing algorithm -- NFDH, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Two-dimensional packing problems: a survey

Cites Work

• 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
• A class of simple stochastic online bin packing algorithms
• A typology of cutting and packing problems
• Shelf Algorithms for Two-Dimensional Packing Problems
• A simple on-line bin-packing algorithm
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Exact Bounds for the Stochastic Upward Matching Problem
• Algorithms for Packing Squares: A Probabilistic Analysis
• Two-dimensional packing: expected performance of simple level algorithms
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Next-fit bin packing with random piece sizes