Questions tagged [subset-sum]
Questions about the NP-complete problem Subset Sum.
117
questions
1
vote
1
answer
434
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
42
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
74
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 ...
- 5,730
1
vote
1
answer
51
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
0
votes
0
answers
43
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 ...
- 159
0
votes
1
answer
50
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
32
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.
0
votes
0
answers
22
views
Maximum Subset Sum with Pairwise Constraints
(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.)
Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
- 11
0
votes
0
answers
20
views
reduction from partition to N3DM or balanced 3 partition problem
I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum.
N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
- 1
3
votes
1
answer
148
views
Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem
The following problem statement is given:
Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
- 43
2
votes
1
answer
55
views
Disjoint Subset Sum Reduction (NP-Complete)
I am using past materials to review for an upcoming assignment and came across this question:
Disjoint Subset Sum:
Input: A set of integers S and a goal g(in the set of natural numbers)
Output: YES if ...
0
votes
0
answers
57
views
Polynomial Time Special Case of Subset Sum Problem
From Chapter 35 of Introduction to Algorithms by Cormen et al.
EXACT-SUBSET-SUM is an exponential-time algorithm in general, although it is a polynomial-time algorithm in the special cases in which $...
- 25
1
vote
1
answer
379
views
Finding equal-sum subsets from two arrays
Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
0
votes
1
answer
84
views
Possible reduction from SUBSET-SUM
Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$.
Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
1
vote
1
answer
181
views
3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
- 11
0
votes
2
answers
65
views
Unlimited use subset sum
Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $...
0
votes
1
answer
45
views
I'm looking for an algorithm to find all subsets of a set S with subset sums between a given min and max
Given a set S of numbers, min and max. Find all sebsets of numbers from S with a subset sum larger or equal to min and smaller or equal to max.
The following article says that there's an algorithm ...
- 11
1
vote
1
answer
35
views
Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
0
votes
1
answer
133
views
Finding number of combinations of numbers from multiple arrays that add up to a given value
Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
- 101
0
votes
0
answers
125
views
Is there linear solution for the hotel problem
You are going on a trip from point $s$ to point $f$, in the way there
are $n$ hotels, $p_1, p_2,..., p_n$ each denotes the number of $km$
from $s$. You must complete the trip by at most $t$ days ($t&...
- 261
1
vote
0
answers
82
views
Is there a pseudopolynomial time algorithm for this subset sum variant?
The subset sum problem is: given a list of $n$ positive integers, and a positive number $T$, find a sub-list with largest sum that is at most $T$. The problem can be found in time polynomial in $n$ ...
- 5,730
1
vote
0
answers
73
views
Given a set, generate all permutations whose sums are less or equal to a given number
I am looking for a way to generate every permutation (so order does matter) of a set of positive numbers whose sum is less than (or equal to) a given limit. I need to find the permutations themselves, ...
- 121
0
votes
0
answers
361
views
Proving the load balancing problem is NP-Complete
The load balancing problem:
Given we have $m\ge3$ machines (servers) $M_{1}, M_{2},\dots,M_{m}$. As input we are given $n$ jobs defined by their processing times: $t_{1},t_{2},\dots,t_{n}\in\mathbb{Q}...
- 49
0
votes
1
answer
177
views
Is SUBSET SUM only for positive integers in P or NP?
Since UNARY SUBSET SUM is in P, and a positive-only SUBSET SUM problem could be represented in unary, I struggle to see why it wouldn't be the case that it is in P, when restricted to positive numbers?...
1
vote
1
answer
36
views
Similar problem to Subset Sum?
I've been trying to search for a problem which I think could be similar to Subset Sum.
The definition of the problem would be as follows:
Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i ...
- 23
0
votes
0
answers
315
views
Python closest subset sum function
I'm writing a closestSubset(s,A) function that takes an integer s and an array of positive integers A and returns an array consisting of elements of A which add up to s. If there is no subset that ...
- 1
2
votes
1
answer
95
views
Is this set covering problem NP-Hard?
Consider this variant of set 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$ for all $k$.
The problem is, divide $S$ ...
- 69
4
votes
1
answer
124
views
Is there a name for this modification to the subset sum problem?
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 ...
- 49
3
votes
1
answer
102
views
Subset sum with only two item types
Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$.
This is a special ...
- 5,730
0
votes
1
answer
97
views
Subset Sum With Interval Integer Target
Define the subset sum with interval integer target problem (SSIITP) as follows:
SSIITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$.
An integer $T$.
SSIITP Output:
True, if ...
- 127
1
vote
3
answers
128
views
Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?
You have an array of floats, for example:
...
1
vote
1
answer
47
views
In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?
This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
2
votes
2
answers
325
views
Complexity of a variant of Subset Sum problem
This is the variant of SSP: Given $n$ positive integer points $a_1, \ldots, a_n$ which are all at most $n$, does there exist a subset $\{a_i\}_{i \in P}$, such that its summation is exactly $n+1$?
My ...
- 23
1
vote
1
answer
645
views
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
- 11
3
votes
2
answers
417
views
Subset Sum With Interval Target
Define the subset sum with interval target problem (SSITP) as follows:
SSITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$.
SSITP Output:
...
- 127
1
vote
0
answers
148
views
Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?
From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
- 127
1
vote
1
answer
683
views
SUBSET SUM reduction to PARTITION
This is the PARTITION problem:
Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets.
This is the SUBSET SUM problem:
Given a multiset S of integers ...
- 113
2
votes
1
answer
177
views
Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows:
given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
- 127
0
votes
1
answer
44
views
Prove SubsetSum is polyequivalent to SubsetSum with surplus
I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv_{P} \text{SubsetSumWithFives}$.
Here is the definition of SubsetSumWithFives.
SUBSETSUMWITHFIVES: ...
- 27
1
vote
1
answer
60
views
Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )
Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$
$$
f(\mathbf{x},n) = \sum_{\sigma_1,...,\...
- 113
0
votes
1
answer
208
views
The subset sum problem is not in P because the question is about lossy compressed data? Why not?
Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression ...
- 33
1
vote
1
answer
415
views
Reduction from SUBSET-SUM to 0-1-INT-PROG
The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.
I am trying to prove that 0-1-INT-PROG ...
- 258
0
votes
1
answer
90
views
Minimum absolute value of subset sums of integer values
$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\...
- 373
0
votes
2
answers
105
views
Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum
I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and ...
- 17
1
vote
1
answer
6k
views
How to prove that the subset sum problem is polynomially reducible to the knapsack problem
I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-...
- 33
1
vote
0
answers
53
views
Get $n^{\mathrm{th}}$ element of sorted subset sums
I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums).
Attempt at solving :
I have ...
0
votes
0
answers
118
views
Subset selection with maximum sum and minimum variance?
So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
0
votes
2
answers
502
views
Reduce Subset-Sum to Sat
Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn }...
- 1
1
vote
1
answer
194
views
Confusion about dynamic programming on unconstrained subset sum vs constrained subset sum
In class, we discussed two problems: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: Given an ...
0
votes
0
answers
42
views
Is is possible to create a SUBSET-SUM instance that each subset is "unique"?
Given a SUBSET-SUM instance $S$ with a weight $W$, is it possible to create, in polynomial time, a new non-empty instance $T$ (at most the same length as $S$) with weight $M$, that for each non-empty ...
- 289