0
$\begingroup$

The problem is the following:

We have a positive integer $w$. A set of positive integers $A$ such that $\forall a \in A$ it's true that $a \leq w$. We search for the minimal integer $x$ such that $w \leq x$ and there is a convex integer combination of the elements of $A$ that is equal to $x$. The problem can clearly be written as an integer program but that's not much help.

My best approach is $O(w)$ in both time and space similar to knapsack's dynamic programming solution.

Could someone suggest a better one?


EDIT: I made 2 mistakes in the formulation. The first is that the combination is not convex only non-negative. The second is the algorithm I mentioned is not $O(w)$ but $O(|A|w)$.

The algorithm is like make an array size of $w$, sign $0$ in it and unsign everything else. Set a variable $\min$ to "infinite". Go through the array and to each signed element add each element of $A$. If it's not smaller than $w$ but smaller than $\min$ it's the new $\min$. If it's smaller than $w$ sign the according element. When we reach the end of the array $\min$ holds the $x$ in question.

Also the problem can be reformulated as a series of $n$ variable diophantine equation so if $A = \{a_{1}, \ldots, a_{n}\}$ and $d = \gcd(a_{1}, \ldots, a_{n})$ then we only need to check for $x \in \mathbb{N}, w \leq x, d \mid x$ if the diophantine equation $\sum_{i = 1}^{n}y_{i} a_{i} = x$ has an all non-negative $Y = \{y_{1}, \ldots, y_{n}\}$ solution.

I don't know the complexity for this second approach. I don't know how long the series can be.

EDIT.2: The length of the series is the smaller problem. Solving any of the above diophantine equations is like solving the subset-sum problem so this approach is not good either.

$\endgroup$
  • 3
    $\begingroup$ what's a convex integer combination ? convexity is usually defined as positive numbers summing to 1. $\endgroup$ – Suresh Venkat Mar 30 '11 at 23:06
  • 3
    $\begingroup$ It's hard to believe the problem can be solved in O(w), which is independent of the size of A. $\endgroup$ – Yoshio Okamoto Mar 30 '11 at 23:37
  • $\begingroup$ I think it will be nice if you provide some background about why you are interested in this problem. $\endgroup$ – Kaveh Mar 31 '11 at 21:41
  • $\begingroup$ I'm pretty sure that this is weakly NP-hard, and if you want to prove it I would look up information on "unbounded knapsack" and/or "knapsack cover." There is a book by Kellerer, Pferschy and Pisinger which goes into a nice amount of detail on such reductions, which should be enough to prove the hardness. $\endgroup$ – daveagp Dec 2 '12 at 5:03
3
$\begingroup$

This is a variant of making change with a given set of coins, for which the knapsack/dynamic programming algorithm seems to be the best that is known. E.g., http://www.algorithmist.com/index.php/Coin_Change

$\endgroup$
  • $\begingroup$ How do you find the smallest x? In the coin change problem x is given. $\endgroup$ – Marcus Ritt Mar 31 '11 at 12:44
  • $\begingroup$ The dynamic programming solution finds all amounts that can be made up to, say, w+max(A). $\endgroup$ – Jack Mar 31 '11 at 13:24
1
$\begingroup$

This is not an answer, but more like a comment. But this is too long to be a comment.

There is a related problem: the computation of the Frobenius number in polynomial time, which is known to be NP-hard (Ramirez-Alfonsin, 1996).

The Frobenius number is defined as follows. Let $a_1,\ldots,a_n$ be positive integers such that $\text{gcd}(a_1,\ldots,a_n)=1$. Then, it's known that there exists a (unique) number $b$ that cannot be represented as any non-negative integer combination of $a_1,\ldots,a_n$, but every integer larger than $b$ can be represented in such a way. This $b$ is called the Frobenius number of $a_1,\ldots,a_n$.

I would expect, if your problem could be solved in polynomial time then we could compute the Frobenius number in polynomial time too. But I have no clue why this should be true for the moment.

$\endgroup$

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.