The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
From MaRDI portal
Publication:3611891
DOI10.1007/978-3-540-74450-4_1zbMath1172.90474OpenAlexW1564665474MaRDI QIDQ3611891
Publication date: 3 March 2009
Published in: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74450-4_1
Related Items (27)
Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty ⋮ Semi-on-line bin packing: a short overview and a new lower bound ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Bin packing with rejection revisited ⋮ Optimal energy-efficient placement of virtual machines with divisible sizes ⋮ Tighter bounds of the First Fit algorithm for the bin-packing problem ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ Exact and approximate methods for the score-constrained packing problem ⋮ Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\) ⋮ Single-machine scheduling with periodic maintenance to minimize makespan revisited ⋮ A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location ⋮ Flowshop scheduling with interstage job transportation ⋮ Three-Bar Charts Packing Problem ⋮ A study on load-balanced variants of the bin packing problem ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ An improved approximation for packing big two-bar charts ⋮ Bin packing game with a price of anarchy of \(\frac{3}{2}\) ⋮ Unnamed Item ⋮ A bin packing game with cardinality constraints under the best cost rule ⋮ An improved approximation scheme for variable-sized bin packing ⋮ Single-machine scheduling with machine unavailability periods and resource dependent processing times ⋮ Constructive heuristics for the canister filling problem ⋮ A 3/2-approximation for big two-bar charts packing ⋮ Two-bar charts packing problem ⋮ Batch scheduling of nonidentical job sizes with minsum criteria ⋮ Better Bin Packing Approximations via Discrepancy Theory ⋮ Three-dimensional bin packing problem with variable bin height
This page was built for publication: The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
