5
$\begingroup$

Let $S = \{\{x_{1},y_{1},z_{1}\},\{x_{2},y_{2},z_{2}\}, \ldots, \{x_{n},y_{n},z_{n}\}\}$ and a target $t$. Let $S_i$ be the subset list $\{x_{i},y_{i},z_{i}\}$. Find a subset sum that sums to $t$ such that one and only one element is chosen from each subset list $S_i$.

I can also imagine this is the same as finding the longest path from $s$ to some sink such that the path costs less than $t$, where the sum of the edges is the same as choosing from each subset list $S_i$.

Is there a name for this problem? Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

I've seen this described as a "a variant of sum of subsets problem" by Arya et al.

Your formulation reminds me of some work I did on the problem of phase identification in electricity networks (e.g. see p118 of my Thesis, p135 of the pdf). Perhaps the references there (from 193 onwards) would be helpful.

$\endgroup$

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.