Tight results for next fit and worst fit with resource augmentation

DOI10.1016/J.TCS.2010.03.019zbMATH Open1207.68453OpenAlexW2053613667MaRDI QIDQ974751FDOQ974751

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

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

zbMATH Keywords

bin packingresource augmentationnext fitworst fit

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Speed is as powerful as clairvoyance
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Online bin packing with resource augmentation
• Fast algorithms for bin packing
• Resource augmentation for online bounded space bin packing

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)