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

DOI10.1007/S10878-005-5481-6MaRDI QIDQ1774522zbMATH OpenOpenAlexFDO

Authors Xiaodong Gu, Yinlong Xu, Guoliang 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 algorithmbin packingNP-hardworst-case performance ratioaverage-case performance ratio

Mathematics Subject Classification ID

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

Recommendations

• Average-case analysis of cutting and packing in two dimensions
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• scientific article; zbMATH DE number 4050974
• Algorithms for Packing Squares: A Probabilistic Analysis

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A stochastic model of bin-packing
• Average-case analysis of cutting and packing in two dimensions
• Average-case analysis of the smart next fit algorithm
• Orthogonal Packings in Two Dimensions
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• Some distributions that allow perfect packing
• 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

Cited in

(3)

• Scheduling non-preemptible jobs to minimize peak demand
• Average-case analysis of cutting and packing in two dimensions
• An exact algorithm for non-preemptive peak demand job scheduling

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

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