Tighter bounds of the First Fit algorithm for the bin-packing problem

DOI10.1016/J.DAM.2010.05.026MaRDI QIDQ602685zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Binzhou Xia, Zhiyi Tan

Publication date 5 November 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.05.026

zbMATH Keywords

bin packingworst case performance ratioFirst Fit

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40)

Recommendations

• scientific article; zbMATH DE number 1560341
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• scientific article; zbMATH DE number 6678949
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• The tight absolute bound of First Fit in the parameterized case

Cites work

• scientific article; zbMATH DE number 51347 (Why is no real title available?)
• scientific article; zbMATH DE number 563208 (Why is no real title available?)
• A new proof for the first-fit decreasing bin-packing algorithm
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• Resource constrained scheduling as generalized bin packing
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• `` Strong NP-Completeness Results

Cited in

(25)

• A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines
• Single-machine scheduling with periodic maintenance to minimize makespan revisited
• Online results for black and white bin packing
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• Analysis of a first-fit algorithm for the capacitated unit covering problem
• A heuristic algorithm for solving triangle packing problem
• Black and White Bin Packing Revisited
• Integrated scheduling on a batch machine to minimize production, inventory and distribution costs
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• Single machine scheduling with batch delivery to multiple customers in a star-shaped network
• The tight absolute bound of First Fit in the parameterized case
• On the absolute approximation ratio for first fit and related results
• k-times bin packing and its application to fair electricity distribution
• scientific article; zbMATH DE number 6678949 (Why is no real title available?)
• Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms
• Two-agent single batch machine scheduling with a fixed capacity distribution
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• Batch scheduling of nonidentical job sizes with minsum criteria
• Renting servers in the cloud: the case of equal duration jobs
• Integrated scheduling of batch production and intermediate delivery with batch-position-based learning effect
• scientific article; zbMATH DE number 3997164 (Why is no real title available?)
• A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts
• Bin packing problem with conflicts and item fragmentation
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
• scientific article; zbMATH DE number 1560341 (Why is no real title available?)

This page was built for publication: Tighter bounds of the First Fit algorithm for the bin-packing problem

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