2 Copy edited. Dressed the naked link.
source | link

subset Subset sum like-like problem over boolean vectors

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

saySay you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on wikipediaWikipedia (modifying it to store maximal sets of subsets rather than true/false): https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solutionPseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

subset sum like problem over boolean vectors

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on wikipedia (modifying it to store maximal sets of subsets rather than true/false): https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

Subset sum-like problem over boolean vectors

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): Pseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

    Tweeted twitter.com/StackCompSci/status/759885835525390336
1
source | link

subset sum like problem over boolean vectors

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on wikipedia (modifying it to store maximal sets of subsets rather than true/false): https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?