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<i$
  • 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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.