What is the run-time of the bin packing approximation algorithm?

The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $$OPT + \log(OPT)$$ bins, and its expected run-time is polynomial in the total number of items. However, I could not understand from the paper, what is the exact polynomial? That is: if there are $$n$$ items with different sizes, what is a number $$k$$ such that the run-time is in $$O(n^k)$$?

• You should check with the authors. Many papers in approximation algorithms rely on various LP solving techniques and the focus is not in the running time. A random person on this forum is unlikely to know (or care) if the authors themselves did not provide a clean bound or tried to. Feb 11, 2021 at 19:10
• I asked the authors, and indeed, they confirmed that they did not try to compute an exact upper bound on the run-time. Feb 24, 2021 at 8:54