Given a set of $n$ positive integer variables, namely $S=\{ s_1, s_2, \cdots, s_n\}$. Find a subset $A \subseteq S$, so that $\Sigma_{s_i \in A} s_i = K$. $K$ is a given parameter.

Unlike the usual one, there is a dependence constraint set here, $D=\{ (a_1, b_1), \cdots, (a_m, b_m) \}$. Here $(a_i, b_i)$ means $a_i \in A$ implies $b_i \in A$. Furthermore, the dependence is not circular. Put another way, if we represent $D$ as a directed graph $G'(V, E)$, that nodes in $G$ corresponds to variable in $S$ and $(a,b) \in D$ iff $(a,b) \in E$, then $G$ is a DAG (acyclic digraph).

Note: Pseudo-polynomial time in terms of $\Sigma_{s \in S} s$ is acceptable for my problem.

I have proved this problem as strongly NP-complete via a reduction from CLIQUE.

Question. I am looking forward to an algorithm that finds a subset $A$ so that $\Sigma_{s_i \in A} s_i$ lies in a neighbourhood of $K$, e.g., between $(1-\alpha)*K$ and $(1+\alpha)*K$.

Thank you very much for your comment and answer. :) Any reference concerning is welcome.

Special case solved: When each variable is implied by at most one another variable, i.e., $\forall_{b \in S}$, $|\{(a,b) \in D \}| \le 1$, it could be solved by DP in $O(n*M*M)$. $M=\Sigma_{s_i \in S} s_i$.

  • 2
    $\begingroup$ I don't see a question. $\endgroup$ – Kaveh Aug 25 '11 at 7:39
  • 1
    $\begingroup$ ps: I am starting to doubt if you really care about the questions you are posting, e.g. I closed this one because you simultaneously cross-posted on MO and commented that you can ask us to reopen if you don't get an answer on MO, you haven't got an answer on MO but you didn't ask us to reopen it. $\endgroup$ – Kaveh Aug 25 '11 at 7:46
  • 1
    $\begingroup$ @Kaveh, Peng: I modified part of the question. Does that make sense? $\endgroup$ – Hsien-Chih Chang 張顯之 Aug 25 '11 at 7:46
  • 1
    $\begingroup$ @Kaveh: Sorry for your doubt. If you look at questions I posted (excepted the closed two), actually I partitioned a lot in the comments other users gave to me. The problem you mentioned, although no answer has shown up at MO, it cause two ups. So I am watching the status of MO, all the time. $\endgroup$ – Peng Zhang Aug 25 '11 at 7:52
  • 2
    $\begingroup$ @Peng could you please take the time to spell out ALL your constraints clearly in the question before we waste time thinking about it, because I don't see anything in the previous versions of this question that even hinted at this non-circularity constraint. $\endgroup$ – Artem Kaznatcheev Aug 25 '11 at 16:59

This is not a solution, but a reference suggestion.

The problem should be (a special case of the decision version of) the partially-ordered knapsack problem. For example, you can look at the following paper and the references therein.

S.G. Kolliopoulos and G. Steiner: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155 (2007) 889-897. http://dx.doi.org/10.1016/j.dam.2006.08.006

| cite | improve this answer | |
  • $\begingroup$ Thank you very much. The partial order in that paper is the inverse of "implication" in my problem. I will take a careful look at your reference. $\endgroup$ – Peng Zhang Aug 25 '11 at 17:54

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.