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)$?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ 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. $\endgroup$– Chandra ChekuriFeb 11, 2021 at 19:10
-
$\begingroup$ I asked the authors, and indeed, they confirmed that they did not try to compute an exact upper bound on the run-time. $\endgroup$– Erel Segal-HaleviFeb 24, 2021 at 8:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
4$\begingroup$ 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. $\endgroup$ Feb 11, 2021 at 14:30