0
$\begingroup$

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$.

$\endgroup$
11
  • 2
    $\begingroup$ I don't see a question. $\endgroup$
    – Kaveh
    Aug 25, 2011 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, 2011 at 7:46
  • 1
    $\begingroup$ @Kaveh, Peng: I modified part of the question. Does that make sense? $\endgroup$ Aug 25, 2011 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, 2011 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$ Aug 25, 2011 at 16:59

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\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, 2011 at 17:54

Your Answer

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

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