What is the run-time of the bin packing approximation algorithm?
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.