<p>According to the definition of polynomial (from Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.):</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>In their Theorem 1.2 they say <em>&quot;The algorithm is randomized and the expected running time is polynomial&quot;</em>. 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.</p>

CC BY-SA 4.0
2021-02-11T14:30:24.970Z
This does not answer the question. The OP knows perfectly well what “polynomial” means. They are asking for the value of the exponent, which is not clear from the paper.
Emil Jeřábek
CC BY-SA 4.0
2021-02-11T14:26:40.000Z
2021-02-11T14:26:40.000Z
purple_lolakos
<p>The best approximation algorithm that I found for the bin packing problem is by <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172" rel="nofollow noreferrer">Hoberg and Rothvoss (SODA, 2017)</a>. In their Theorem 1.2, they mention that their algorithm finds a solution with at most <span class="math-container">$OPT + \log(OPT)$</span> 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 <span class="math-container">$n$</span> items with different sizes, what is a number <span class="math-container">$k$</span> such that the run-time is in <span class="math-container">$O(n^k)$</span>?</p>

CC BY-SA 4.0
2021-02-11T19:10:53.597Z
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.
Chandra Chekuri
CC BY-SA 4.0
2021-02-24T08:54:05.513Z
I asked the authors, and indeed, they confirmed that they did not try to compute an exact upper bound on the run-time.
Erel Segal-Halevi
<approximation-algorithms><time-complexity>
What is the run-time of the bin packing approximation algorithm?
Erel Segal-Halevi
# What is the run-time of the bin packing approximation algorithm?

(Asked by: username_0 on 2021-02-11)

The best approximation algorithm that I found for the bin packing problem is by [Hoberg and Rothvoss (SODA, 2017)](https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172). 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)$?

**Tags:** approximation-algorithms, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: I asked the authors, and indeed, they confirmed that they did not try to compute an exact upper bound on the run-time.  

---

## 1 answers

### Answer by username_2 on 2021-02-11. Score: -2

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.

> **Comments:**
> **username_3**: This does not answer the question. The OP knows perfectly well what “polynomial” means. They are asking for the value of the exponent, which is not clear from the paper.  

---

