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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.