Questions tagged [subset-sum]
Questions about the NP-complete problem Subset Sum.
123 questions
0
votes
0
answers
91
views
Is this reduction from Exact 1-in-3-SAT to Subset Sum using Horowitz and Sahni's algorithm known?
I'm exploring a reduction from Exact 1-in-3-SAT (x3SAT) to the Subset Sum problem that allows the use of the Horowitz and Sahni algorithm, achieving a time complexity of
$\mathcal{O^*}(2^{𝑛/2})$ for ...
- 2,511
0
votes
0
answers
22
views
Reduction for Subset Maximizing Profit
Consider a set of elements $\mathcal{E}$ where we define Profit for each pair of elements $e_1, e_2 \in \mathcal{E}$ as $P(e_1, e_2)$. The objective is to find a subset $\mathcal{E}_s$ such that the ...
- 101
1
vote
2
answers
59
views
prove AP-SUM is NP-complete
EDIT: I had a translation error. Instead of "unuary", it's binary.
AP-SUM is the language defined in the following way:
A word in the language AP-SUM is a pair <S, t>,
so that S is a ...
- 141
0
votes
0
answers
30
views
Do large integers increase the expressiveness of $\mathsf{SUBSET-SUM}$?
We can consider any set $A$ of integers as a nondeterministic "subset-sum circuit" for strings represented as numbers in some range $[-2^N, 2^N]$, accepting an integer $n$ within this range ...
3
votes
1
answer
57
views
Harder version of the k-partition problem
Given a sequence $q_1, \ldots, q_n$ of numbers, decide if the set $I=\{1,\ldots,n\}$ can be partitioned into $k$ sets $I_1, \ldots, I_k$ such that $\sum_{i\in I_1} q_i=\sum_{i\in I_2} q_i = \dots = \...
- 555
1
vote
0
answers
32
views
NP-hardness of subset sum of multiple supersets
Given the following problem:
Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$
Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
- 161
0
votes
0
answers
58
views
Why does this approach not work on the SubSet Sum Problem?
I was reading this post, and in it I learned how to make difficult instances of the SubSet Sum Problem.
There the guy who responded to the post says that it is necessary to have density 1.0 and all ...
- 1
1
vote
1
answer
119
views
Subset ${\tt XOR}$ problem
Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.
Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
1
vote
1
answer
503
views
Find the smallest subarray with sum larger than a threshold
Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
- 109
0
votes
0
answers
53
views
HAMILTONIAN PATH AND SUBSETSUM
If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P?
...
- 1
3
votes
0
answers
92
views
Subset sum problem with big items
Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
- 6,164
1
vote
1
answer
66
views
Is this variant of multiset covering problem NP-hard?
Consider this variant of multiset covering problem.
Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
- 11
1
vote
0
answers
81
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 169
0
votes
1
answer
90
views
Efficient algorithm for finding the target sum
Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
- 1
0
votes
0
answers
52
views
List of weakly NP-HARD problems
I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
