The tight absolute bound of First Fit in the parameterized case

DOI10.1016/J.TCS.2015.06.046MaRDI QIDQ2355708zbMATH OpenOpenAlexFDO

Authors György Dósa

Publication date 24 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.046

zbMATH Keywords

absolute approximation ratiobin packingFirst Fit

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 6678949 (Why is no real title available?)
• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 3557207 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimal analysis of best fit bin packing
• Resource constrained scheduling as generalized bin packing
• The design of approximation algorithms
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(6)

• On the absolute approximation ratio for first fit and related results
• scientific article; zbMATH DE number 1560341 (Why is no real title available?)
• Several methods of analysis for cardinality constrained bin packing
• Several methods of analysis for cardinality constrained bin packing
• Tighter bounds of the First Fit algorithm for the bin-packing problem
• Semi-online models for cardinality constrained bin packing

This page was built for publication: The tight absolute bound of First Fit in the parameterized case

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