Optimal analysis of Best Fit bin packing

Abstrakt

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.

Klíčová slova

• bin packing
• approximation algorithms