TAOCP 7.2.2.2 Exercise 169
Working
Section 7.2.2.2: Satisfiability
Exercise 169. ▶ [HM30] (T. Ahmed, O. Kullmann.) Excellent results have been obtained in some problems when the branch variable in step L3 is chosen to minimize the quantity $\tau(H(l), H(\bar{l}))$, where $\tau(a, b)$ is the positive solution to $\tau^{-a} + \tau^{-b} = 1$. (For example, $\tau(1, 2) = \phi \approx 1.62$ and $\tau(\sqrt{2}, \sqrt{2}) = 2^{1/\sqrt{2}} \approx 1.63$, so we prefer $(1, 2)$ to $(\sqrt{2}, \sqrt{2})$.) Given a list of pairs of positive numbers $(a_1, b_1), \ldots, (a_n, b_n)$, what's an efficient way to determine an index $j$ that minimizes $\tau(a_j, b_j)$, without computing logarithms?
Verified: no
Solve time: 59s
Working