3
$\begingroup$

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem

After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden Ratio) the algorithm takes a lot of time to printout the result.

When the ratio r is so close to ϕ , I noticed that : V / Vtotal = (V + Vtotal) / V (which represents the geometric relationship of the two quantities V and Vtotal in the Golden Ratio).

However, few of the instances having a ratio r > ϕ can take too long to print the results too.

So can this problem be related to ϕ or not?

PS: I got the idea of comparing it to ϕ after checking this answer Lower bound on running time for solving 3-SAT if P = NP

Improve this question
$\endgroup$
2
  • $\begingroup$ I guess there is no difference between $\phi$ or $\phi \pm \epsilon$. $\endgroup$
    – Raphael
    Commented Apr 27, 2016 at 11:11
  • $\begingroup$ @Raphael you are right (ps: I edited my question and added another information I noticed when testing) $\endgroup$
    – AIri
    Commented Apr 27, 2016 at 13:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.