<p>I don't think you're going to get a single answer.  I expect there are multiple algorithms, each most effective in a different portion of the problem space.  Beyond integer linear programming and methods for finding integer relations, I expect that many of the algorithms for <a href="https://en.wikipedia.org/wiki/Partition_problem#Exact_algorithms" rel="nofollow noreferrer">the partition problem</a> or <a href="https://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithms" rel="nofollow noreferrer">subset sum problem</a> can potentially be adapted to your problem as well.</p>

CC BY-SA 4.0
2024-06-19T22:20:42.353Z
2024-06-19T22:20:42.353Z
D.W.
<p>Let <span class="math-container">$x_1,\cdots,x_n,k$</span> be integers such that <span class="math-container">$|k|\le\sum_{i=1}^n|x_i|$</span>.</p>
<p>What is the quickest known algorithm to determine <span class="math-container">$w_i\in\{-1,0,1\}$</span> such that <span class="math-container">$k=\sum_{i=1}^nw_ix_i$</span> where they exist?</p>
<p>What is its asymptotic as <span class="math-container">$n\to\infty$</span>?</p>
<p><a href="https://en.wikipedia.org/wiki/Integer_relation_algorithm" rel="nofollow noreferrer">These algorithms</a> apply more generally to <span class="math-container">$w_i\in\Bbb Z$</span> and <span class="math-container">$x_i\in\Bbb R$</span> so perhaps this case has a faster algorithm.</p>
<p><sub> Previously posted on <a href="https://or.stackexchange.com/q/12181/123">Operations Research Stack Exchange</a> with no response.</sub></p>

CC BY-SA 4.0
2024-06-24T09:35:27.200Z
Just to note, it's possible to solve the problem in $\approx 3^{n/2}$ time using an algorithm similar to the $2^{n/2}$-time meet-in-the-middle algorithm for Subset Sum.
Huck Bennett
<ds.algorithms>
Quickest known integer relation algorithm in the case of signs
TheSimpliFire
# Quickest known integer relation algorithm in the case of signs

(Asked by: username_0 on 2024-06-19)

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](https://en.wikipedia.org/wiki/Integer_relation_algorithm) apply more generally to $w\_i\in\Bbb Z$ and $x\_i\in\Bbb R$ so perhaps this case has a faster algorithm.

Previously posted on [Operations Research Stack Exchange](https://or.stackexchange.com/q/12181/123) with no response.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Just to note, it's possible to solve the problem in $\approx 3^{n/2}$ time using an algorithm similar to the $2^{n/2}$-time meet-in-the-middle algorithm for Subset Sum.  

---

## 1 answers

### Answer by username_2 on 2024-06-19. Score: 1

I don't think you're going to get a single answer. I expect there are multiple algorithms, each most effective in a different portion of the problem space. Beyond integer linear programming and methods for finding integer relations, I expect that many of the algorithms for [the partition problem](https://en.wikipedia.org/wiki/Partition_problem#Exact_algorithms) or [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithms) can potentially be adapted to your problem as well.


---

