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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.