Bin Packing Approximation

In this video, we discuss the Bin Packing problem. We show that Bin Packing allows for a 1.5-approximation. We also present a matching lower bound. So both upper and lower bounds are optimal, unless P is equal to NP.