# Lower bound for Yao's algorithm on general addition chains?

An addition chain of size $$n$$ for given integers $$n_1,n_2\dots ,n_p$$ is a sequence of integers $$k_1,k_2\dots ,k_n$$ such that

• $$k_1=1$$,
• for all $$i$$ $$(2\le i\le m)$$ we have $$k_i=k_j+k_m$$ for some $$1\le j,m
• and $$\{n_1,n_2\dots ,n_p\}\subseteq \{k_1,k_2\dots k_n\}$$.

The general addition chain problem is the following:

Given: Numbers $$n_1,n_2,\dots,n_p$$

Problem: Compute a smallest addition chain for $$n_1,n_2,\dots,n_p$$.

This problem is known to be $$\mathsf{NP}$$-hard by [Dow81]. However, Yao [Yao76] presented an algorithm which on any input produces an addition chain of size $$\log N +c\cdot\sum_{i=1}^p\frac{\log n_i}{\log \log (n_i+2)}\le \log N +\frac{cp\log N}{\log \log (N+2)},$$ where $$N=\max_i(n_i)$$ and $$c$$ is a constant. In [Cha05] it is now claimed that this is an approximation algorithm for the general addition chain problem of ratio $$O\left(\frac{\log\left(\sum_i n_i\right)}{\log\log\left(\sum_i n_i\right)}\right),$$ i.e., Yao's algorithm produces for each input a chain which is at most by this factor larger than a smallest addition chain.

Now my question: Is there a lower bound on the approximation ratio of Yao's algorithm, e.g. is there a family of inputs such that Yao's algorithm produces addition chains which are by the described factor larger than a shortest addition chain?





[Dow81]: P. Downey, B. Leony, and P. Sethi, "Computing Sequences with Addition Chains", SIAM J. Computing, vol. 11, pp. 638-696, 1981

[Yao76]: A. C.-C. Yao, “On the evaluation of powers”, SIAM J. Comput., vol. 5, no. 1, pp. 100–103, 1976

[Cha05]: M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, A. Shelat, "The Smallest Grammar Problem", IEEE Transactions on Information Theory. 51 (7): 2554–2576, 2005