Best Fit Bin Packing with Random Order Revisited [Arindam Khan, CSA]

The bin packing problem is a fundamental problem in combinatorial optimization, where a collection of items has to be packed into a minimum number of bins. It finds numerous applications in urban planning, logistics, powerplants, scheduling, etc.  The goal of online algorithms is to solve the problem without the complete knowledge of the future. We study the performance guarantee of such online algorithms and made progress after two decades.


S. Albers, A. Khan, L. Ladewig, Best Fit Bin Packing with Random Order Revisited. MFCS (Mathematical Foundations of Computer Science) 2020. 7:1-7:15. (Recipient of best paper award, sponsored by European Association for Theoretical Computer Science (EATCS)).


Click image to view enlarged version

Scroll Up