Best Fit Bin Packing with Random Order Revisited

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.

References:

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)).

Website: https://www.csa.iisc.ac.in/~arindamkhan/