# Branch and Bound running time and golden ratio

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

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