2
$\begingroup$

Consider the following problem:

Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a subset $AS$ of $A$ so that the weight of $AS$ is less than $W$ and the value of $AS$ (the sum of the value of its items) is maximized is the 0/1 Knapsack Problem

Now, consider a deviation from it where the items in $A$ have certain dependency relationships between each other, and these dependencies can be captured by a directed acyclic graph $G(A, E)$. The value of the set $AS$ is no longer the sum of the value of the items in $AS$. For each item in $AS$, its value depends on which other items are also in $AS$.

More formally, this is how we calculate the value of an item $v$ in $AS$. Let $a$ be the a closest ancestor of $v$ in $G$ that is also in $AS$. Then the contribution of $v$ to the value of $AS$ would be its own value, plus the value of all the ancestors in the path between $v$ and $a$. (Since this is a DAG, there could be many of these ancestors. See formalization below).

This problem has important applications in computational workflow systems where you have limited storage, and you want to optimize the computational time of running a workflow (represented by a DAG) by storing some of the intermediate datasets for future use.

My questions

The problem is obviously NP-Hard because the Knapsack problem can be reduced to it. I have a feeling that it is likely that no pseudo-polynomial algorithm exists for it. Do you know of a problem that I could use to reduce to my problem to confirm those feelings? Or do you think that it is possible to produce a pseudo-polynomial algorithm for this?

EDIT: FORMALIZATION ON HOW TO COMPUTE VALUE OF $AS$

To succinctly define the value of $AS$ I will add to the notation from above a little bit. Let $v(z_i)$ be equivalent to $v_i$ from above. Then $v(z_i|AS)$ reads: value of node $z_i$ given answer set $AS$.

  • If $z_i \in AS$, then $v(z_i|AS)=0$.
  • Otherwise, if $z_i \not\in AS$, $v(z_i|AS) = v(z_i) + \sum_{z_j \in parents(z_i)}{v(z_j|AS)}$

Those two definitions are enough to then say that:

$value(AS) = \sum_{z_i \in AS}{v(z_i|AS-\{z_i\})}$

END OF EDIT

$\endgroup$
  • $\begingroup$ In the value calculation, if $v$ has multiple ancestors of maximal distance, do we take the maximum-valued path or all paths from the ancestors to $v$ (or all shortest paths, or the maximum-valued path for each ancestor or something else)? Also, do we include the value of $a$ but not the value of $v$? And, in a diamond DAG, if we get the top and bottom nodes do we score both parents of $v$? Would be helpful if there's a resource describing how this value is calculated, or if we can formalize that a little more. $\endgroup$ – William Macrae Apr 22 '15 at 0:14
  • $\begingroup$ Thanks for pointing that out. Edit added to the question. $\endgroup$ – ASDF Apr 22 '15 at 3:51

Your Answer

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

Browse other questions tagged or ask your own question.