A problem of sum set and difference set

73 Views Asked by At

Given a set of $N$ distinct positive integers $ {A}=\left\{a_1,a_2,\cdots,a_N\right\}$. Denote the sum set of elements in $A$ as $B=\left\{a_m+a_n|a_m,a_n\in A \right\}$. Then, denote the difference set of elements in $B$ as $C=\left\{b_i-b_j, |b_i,b_j\in B \right\}$. Denote the maximum number in $C$ as $x$. I want to find a set $A$ containing as few elements as possible, i.e., minimize $N$, subject to the constraints that (a) the set $C$ contains all consecutive integers from $-x$ to $x$, and (b) $x$ is as large as possible.

Also, we can write $C=\left\{ (a_{n_1}+a_{n_2})-(a_{n_3}+a_{n_4})|a_{n_1},a_{n_2},a_{n_3},a_{n_4}\in A\right\}$. I am designing an algorithm for searching the elements in $A$, and I am wondering if there is any approach to reduce computation complexity. Are there any good research papers on this topic?