Optimal analysis of Best Fit bin packing

Abstract

We prove that also the absolute approximation ratio for BestFit bin packing is exactly 1.7, improving the previous bound of 1.75. Furthermore we show matching lower bounds.

Keywords

• bin packing
• approximation algorithms