Performance analysis and improvement for some linear on-line bin-packing algorithms

DOI10.1023/A:1019577921700MaRDI QIDQ1810864zbMATH OpenOpenAlexFDO

Authors Xiaodong Gu, J. Gu, Yunjae Jung, Liusheng Huang, Guoliang Chen

Publication date 9 June 2003

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

Full work available at URL https://doi.org/10.1023/a:1019577921700

zbMATH Keywords

approximation algorithmsaverage-case performance ratiobin packing problemNPC problemworst-case performance ratio

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 4773
• An improved lower bound for on-line bin packing algorithms
• On-line bin packing in linear time
• The average-case analysis of some on-line algorithms for bin packing
• Multidimensional on-line bin packing: Algorithms and worst-case analysis
• An on-line algorithm for multidimensional bin packing
• A new and improved algorithm for online bin packing
• Multidimensional on-line bin-packing: An algorithm and its average-case analysis
• On-line algorithms for cardinality constrained bin packing problems
• An on-line algorithm for variable-sized bin packing

Cited in

(5)

• Average-case analysis of the modified harmonic algorithm
• On the online bin packing problem
• scientific article; zbMATH DE number 4773 (Why is no real title available?)
• On-line bin packing in linear time
• MINIMUM AREA CONVEX PACKING OF TWO CONVEX POLYGONS

This page was built for publication: Performance analysis and improvement for some linear on-line bin-packing algorithms

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