1
$\begingroup$

Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$ (x_1\cdot y_1) + (x_1\cdot y_1) + \cdots + (x_{n-1}\cdot y_{n-1}) + (x_n\cdot y_n) = m $ i.e. is there an assignment of variables $y_i$ such that the equation is true? After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?

$\endgroup$
3
$\begingroup$

Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x_1,\ldots,x_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.

$\endgroup$
  • $\begingroup$ Is this true even if $m,x_i$ and $y_i$ can be BOTH positive and negative integers? $\endgroup$ – Tyler Durden Nov 12 '14 at 10:26
  • $\begingroup$ Yes, and in fact you have to allow the $y_i$ to be positive, negative, or zero. Otherwise this criterion is not correct. $\endgroup$ – Yuval Filmus Nov 12 '14 at 15:15
  • $\begingroup$ My apologies, but i actually got my criteria wrong. I have updated the answer - the variables are now limited to N instead of Z. I assume that the GCD mechanism no longer works? $\endgroup$ – Tyler Durden Nov 20 '14 at 18:01
  • $\begingroup$ This is related to the coin problem (en.wikipedia.org/wiki/Coin_problem). It's better if you rolled back your change and asked a new question, so that this answer remains relevant. $\endgroup$ – Yuval Filmus Nov 20 '14 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.