Let $x_1,\cdots,x_n,k$ be integers such that $|k|\le\sum_{i=1}^n|x_i|$.

What is the quickest known algorithm to determine $w_i\in\{-1,0,1\}$ such that $k=\sum_{i=1}^nw_ix_i$ where they exist?

What is its asymptotic as $n\to\infty$?

These algorithms apply more generally to $w_i\in\Bbb Z$ and $x_i\in\Bbb R$ so perhaps this case has a faster algorithm.

  • $\begingroup$ In the case the variables are integer, one possible way would be similar to finding the solutions on the system of linear equations. I am unsure about its algorithm, but it can be done by any standard MIP/MINLP solver. $\endgroup$
    – A.Omidi
    Commented Jun 16 at 6:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.