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 "The algorithm is randomized and the expected running time is polynomial". 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.