7
$\begingroup$

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
  2. Upper Bounds on the Number of Solutions of Binary Integer Programs
$\endgroup$
2
  • $\begingroup$ Well, Knapsack Problems 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… $\endgroup$ Mar 5, 2012 at 12:33
  • $\begingroup$ Nevermind – provided a solution of my own below ;-) $\endgroup$ Mar 5, 2012 at 13:18

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Mar 5, 2012 at 13:21
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2012 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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