<p>Shooting from the hip here, but I think this might, in fact, be a simple problem to solve in pseudopolynomial time, using dynamic programming (DP). Not sure if that's acceptable, or if you need a polynomial-time algorithm?</p>

<blockquote>
  <p><strong>A brief detour:</strong> You assume that the optimal value is known, and that $\varepsilon&gt;0$, and I don't know how hard the given counting problem is. If you made no such assumptions, however, you're basically left with (an obvious reduction from) the decision-version of 0-1-knapsack, which is, of course, NP-complete. The question, of course, is whether the additional assumptions are enough to “rescue” the problem from hardness.</p>
</blockquote>

<p>My intuition comes from the fact that DP formulations in general are equivalent to path problems (such as shortest/longest path, or the number of paths) in DAGs. I think counting the number of paths from some node $s$ (representing the zero-capacity knapsack and the empty subset of items) that are “long enough,” given some threshold (in your case, $(1-\varepsilon)v$) is quite straightforward as well.</p>

<p>You can formulate it recursively, as follows. Let $G=(V,E)$ be your DAG, let $w(u,v)$ be the edge weight function, let $\ell_\delta(v)$ be the number of $s$-paths ending at node $v$ with a length of at least $\delta$. You then have:</p>

<p>\begin{equation}
\ell_\delta(v) =
\begin{cases}
0 &amp; \text{if $v=s \land \delta &gt; 0\,$;} \\
1 &amp; \text{if $v=s \land \delta \leq 0\,$;} \\
\sum_{u:(u,v)\in E} \ell_{\delta-w(u,v)}(u)&amp; \text{otherwise.}
\end{cases}
\end{equation}</p>

<p>I'm implicitly assuming that all nodes lie on a path from $s$, as they will in your case, but for nodes beside $s$ that don't have predecessors, the sum will simply be an empty sum, which can be assumed to be zero. To implement this, just memoize it or turn it “upside down” and fill the appropriate array.</p>

<p>In the knapsack case, you'd only have two predecessors $u$ to sum over, of course (i.e., the ones representing the solutions with and without the object under consideration in node $v$). The solution will simply be $\ell_{(1-\varepsilon)v}(t)$, where $t$ is the final “corner” of your matrix, with full capacity and the full set of items.</p>

CC BY-SA 3.0
2012-03-05T13:21:17.787Z
Given that you're working with approximations, this might not be what you're looking for, of course; if you have the time for a full pseudopolynomial solution like this, you could just as easily find the optimum, obviously. But I’m guessing that to solve this problem in polynomial time, you'd yet again need an approximation. (I.e., an approximation to your counting problem.)
Magnus Lie Hetland
CC BY-SA 3.0
2012-03-05T16:48:15.443Z
Thank you for reply. Your intuition seems aligned with an idea in one of the two papers I have already found. Nevertheless, I would like to explore the bibliography in more depth.
Dimitris Leventeas
CC BY-SA 3.0
2012-03-05T13:16:36.917Z
2012-03-05T15:37:58.370Z
2012-03-05T15:37:58.370Z
Magnus Lie Hetland
<p>I am trying to find some related bibliography in the field. If, by chance, my question is easy enough though, a direct answer is more than welcome.</p>

<p>The problem is: Given that the best possible solution for our instance has value $v$, how many solutions have value at least (1 - ε)v? Of course, they should satisfy the constraint of the weight.</p>

<p>I face some difficulties finding the related bibliography in particular, because it seems it is quite often to consider the problem without trying to maximize an associated value but just trying to find the number of solutions in the corresponding linear Diophantine's equation. </p>

<p>Knapsack as in:</p>

<p>maximize $\sum_{i=1}^{n}u_ix_i$,</p>

<p>subject to $\sum_{i=1}^{n}w_ix_i \le W$, $x_i = {0, 1}$</p>

<p>Although, it does not really matter whether it is the 0-1, bounded or the unbounded problem.</p>

<p>What I have found so far and is somewhat related is:</p>

<ol>
<li><a href="http://www.crt.umontreal.ca/~quosseca/pdf/30-0624.pdf">Counting Solutions of CSPs: A Structural Approach</a></li>
<li><a href="http://www.cs.brown.edu/people/serdark/cpaior-10.pdf">Upper Bounds on the Number of Solutions of Binary Integer Programs</a></li>
</ol>

CC BY-SA 3.0
2012-03-05T12:33:25.147Z
Well, [Knapsack Problems](http://www.amazon.com/Knapsack-Problems-Hans-Kellerer/dp/3540402861) by Kellerer, Pferschy and Pisinger is a good book about knapsack problems, including approximations, though I don't have it here right now, so I don't know if it answers your specific question…
Magnus Lie Hetland
CC BY-SA 3.0
2012-03-05T13:18:46.853Z
Nevermind – provided a solution of my own below ;-)
Magnus Lie Hetland
<cc.complexity-theory><reference-request><counting-complexity>
Bibliography needed: How many "good" solutions for Knapsack?
Dimitris Leventeas
# Bibliography needed: How many "good" solutions for Knapsack?

(Asked by: username_0 on 2012-03-04)

I am trying to find some related bibliography in the field. If, by chance, my question is easy enough though, a direct answer is more than welcome.

The problem is: Given that the best possible solution for our instance has value $v$, how many solutions have value at least (1 - ε)v? Of course, they should satisfy the constraint of the weight.

I face some difficulties finding the related bibliography in particular, because it seems it is quite often to consider the problem without trying to maximize an associated value but just trying to find the number of solutions in the corresponding linear Diophantine's equation.

Knapsack as in:

maximize $\sum\_{i=1}^{n}u\_ix\_i$,

subject to $\sum\_{i=1}^{n}w\_ix\_i \le W$, $x\_i = {0, 1}$

Although, it does not really matter whether it is the 0-1, bounded or the unbounded problem.

What I have found so far and is somewhat related is:

1. [Counting Solutions of CSPs: A Structural Approach](http://www.crt.umontreal.ca/~quosseca/pdf/30-0624.pdf)
2. [Upper Bounds on the Number of Solutions of Binary Integer Programs](http://www.cs.brown.edu/people/serdark/cpaior-10.pdf)

**Tags:** cc.complexity-theory, reference-request, counting-complexity

> **Comments:**
> **username_1**: Well, [Knapsack Problems](http://www.amazon.com/Knapsack-Problems-Hans-Kellerer/dp/3540402861) by Kellerer, Pferschy and Pisinger is a good book about knapsack problems, including approximations, though I don't have it here right now, so I don't know if it answers your specific question…  
> **username_1**: Nevermind – provided a solution of my own below ;-)  

---

## 1 answers

### Answer by username_1 on 2012-03-05. Score: 2

Shooting from the hip here, but I think this might, in fact, be a simple problem to solve in pseudopolynomial time, using dynamic programming (DP). Not sure if that's acceptable, or if you need a polynomial-time algorithm?

> **A brief detour:** You assume that the optimal value is known, and that $\varepsilon>0$, and I don't know how hard the given counting problem is. If you made no such assumptions, however, you're basically left with (an obvious reduction from) the decision-version of 0-1-knapsack, which is, of course, NP-complete. The question, of course, is whether the additional assumptions are enough to “rescue” the problem from hardness.

My intuition comes from the fact that DP formulations in general are equivalent to path problems (such as shortest/longest path, or the number of paths) in DAGs. I think counting the number of paths from some node $s$ (representing the zero-capacity knapsack and the empty subset of items) that are “long enough,” given some threshold (in your case, $(1-\varepsilon)v$) is quite straightforward as well.

You can formulate it recursively, as follows. Let $G=(V,E)$ be your DAG, let $w(u,v)$ be the edge weight function, let $\ell\_\delta(v)$ be the number of $s$-paths ending at node $v$ with a length of at least $\delta$. You then have:

\begin{equation}
\ell\_\delta(v) =
\begin{cases}
0 & \text{if $v=s \land \delta > 0\,$;} \\
1 & \text{if $v=s \land \delta \leq 0\,$;} \\
\sum\_{u:(u,v)\in E} \ell\_{\delta-w(u,v)}(u)& \text{otherwise.}
\end{cases}
\end{equation}

I'm implicitly assuming that all nodes lie on a path from $s$, as they will in your case, but for nodes beside $s$ that don't have predecessors, the sum will simply be an empty sum, which can be assumed to be zero. To implement this, just memoize it or turn it “upside down” and fill the appropriate array.

In the knapsack case, you'd only have two predecessors $u$ to sum over, of course (i.e., the ones representing the solutions with and without the object under consideration in node $v$). The solution will simply be $\ell\_{(1-\varepsilon)v}(t)$, where $t$ is the final “corner” of your matrix, with full capacity and the full set of items.

> **Comments:**
> **username_1**: Given that you're working with approximations, this might not be what you're looking for, of course; if you have the time for a full pseudopolynomial solution like this, you could just as easily find the optimum, obviously. But I’m guessing that to solve this problem in polynomial time, you'd yet again need an approximation. (I.e., an approximation to your counting problem.)  
> **username_0**: Thank you for reply. Your intuition seems aligned with an idea in one of the two papers I have already found. Nevertheless, I would like to explore the bibliography in more depth.  

---

