CFAL Alumnus Anish Hebbar Makes Strides in Bin Packing Research: Featured in Arindam Khan’s SODA 2024 Paper
In the photo, KVN is seen on the left, Anish Hebbar is in the middle, and Arindam Khan is on the right, captured together in the lab in 2022.
A paper titled “Bin Packing under Random-Order: Breaking the Barrier of 3/2” has been accepted for publication at the ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).
This is a result which made me really happy.
Bin Packing is a classical NP-hard problem, where items with associated sizes must be packed in the minimum number of unit-capacity bins. It has been studied by many stalwarts: from Turing Award winner Richard Karp, Jeff Ullman, Andrew Yao, to other legends such as Peter Shor, Narendra Karmarkar, David Johnson, etc.
Though Bin Packing admits theoretically good approximation ratios (called APTAS), the best-known practical algorithm is modified-first-fit, which has an approximation guarantee of 1.19. Kenyon, in 1996, conjectured that randomized Best-Fit might be the best practical algorithm with approximation guarantee of 1.15. In this algorithm, we consider items in a randomly permuted order and then apply Best-Fit (pack an item to the fullest bin where it fits). She showed an upper bound of 1.5 and a lower bound of 1.08. However, despite the simplicity of the algorithm and efforts by many experts over the last three decades, the conjecture remained one of the major unsolved open problems in the area.
I first started working on this problem in 2017 during my postdoc at TU Munich. We could only solve a special case then. Then in 2020, I visited Chile and worked on this problem with Jiri Sgall. We had some nice ideas, but eventually, they did not work out. Since then, every year, I used to spend some time on the problem. In 2021, I started working with my PhD student KVN Sreenivas and made some more progress. However, the final piece was still missing.
An undergrad student Anish Hebbar (BS student at IISc) joined me for his Bachelor’s thesis in 2022. Anish is exceptionally smart (received 100/100 in all my offered courses at IISc). Finally, Anish made some crucial observations leading us to progress towards the conjecture by providing an upper bound of 1.5-10^{-10} and a lower bound of 1.144.
Though the dent might look small, it took sophisticated mathematics of nearly 50 pages. This became part of Anish’s Bachelor’s thesis. It is probably the first SODA paper by an IISc undergrad (extremely rare for undergrads to publish in SODA, which is the top conference in algorithms). Anish has just joined Duke University for his PhD.
We are still far from settling the conjecture completely. Hopefully, after our results, we will see some quick progress now. Though many researchers take pride in paper counts and citations, I feel nothing can beat the thrill of making progress on your favorite problems.
[With coauthors KVN (left) and Anish (middle) in my lab in 2022]
