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)$?
According to the definition of polynomial (from Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.):

An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., T(n) = O(n^k) for some positive constant k.

In their Theorem 1.2 they say &quot;The algorithm is randomized and the expected running time is polynomial&quot;. So their are meaning that the algorithm proposed is randomized (non deterministic), but its running time is polynomial, since is within a sum over the bins.