Tight results for next fit and worst fit with resource augmentation

DOI10.1016/J.TCS.2010.03.019MaRDI QIDQ974751zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Asaf Levin, Joan Boyar

Publication date 7 June 2010

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

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

zbMATH Keywords

bin packingresource augmentationnext fitworst fit

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• On the absolute approximation ratio for first fit and related results
• Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing
• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
• Optimal analysis of best fit bin packing
• scientific article; zbMATH DE number 563208

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A simple on-line bin-packing algorithm
• Fast algorithms for bin packing
• Online bin packing with resource augmentation
• Resource augmentation for online bounded space bin packing
• Speed is as powerful as clairvoyance
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(5)

• Comparing the costs of any fit algorithms for bin packing
• The resource dependent assignment problem with a convex agent cost function
• On the absolute approximation ratio for first fit and related results
• Relative Worst-Order Analysis: A Survey
• Pipelined model parallelism: complexity results and memory considerations

This page was built for publication: Tight results for next fit and worst fit with resource augmentation

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