Average-case performance analysis of a 2D strip packing algorithm -- NFDH

DOI10.1007/s10878-005-5481-6zbMath1066.90103OpenAlexW2028273855MaRDI QIDQ1774522

Yinlong Xu, Xiaodong Gu, Guo-Liang Chen

Publication date: 17 May 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-005-5481-6

zbMATH Keywords

approximation algorithmNP-hardbin packingworst-case performance ratioaverage-case performance ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (2)

Scheduling non-preemptible jobs to minimize peak demand ⋮ An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling

Cites Work

• Unnamed Item
• Average-case analysis of cutting and packing in two dimensions
• The average-case analysis of some on-line algorithms for bin packing
• Average-case analysis of the smart next fit algorithm
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Some distributions that allow perfect packing
• A stochastic model of bin-packing
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2

This page was built for publication: Average-case performance analysis of a 2D strip packing algorithm -- NFDH