Questions tagged [subset-sum]
Questions about the NP-complete problem Subset Sum.
97
questions
0
votes
0
answers
41
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&...
- 241
1
vote
0
answers
43
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,726
1
vote
0
answers
22
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
51
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
51
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
26
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
108
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
73
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
5
votes
1
answer
85
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 ...
- 51
3
votes
1
answer
79
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,726
0
votes
1
answer
62
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 ...
1
vote
2
answers
56
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
42
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
218
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
181
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
221
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:
...
1
vote
0
answers
77
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 ...
1
vote
1
answer
166
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 ...
- 13
2
votes
1
answer
111
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 ...
0
votes
1
answer
40
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
40
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
64
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
120
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 ...
- 248
0
votes
1
answer
78
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
91
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
0
votes
1
answer
2k
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-...
- 13
1
vote
0
answers
52
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
94
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
239
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
128
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
40
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
0
votes
1
answer
60
views
How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?
An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset.
However, I want to know, is it possible to create a new instance $T$, ...
- 289
0
votes
1
answer
88
views
Multi-dimensional Knapsack with Minimum Value constraints for Dimensions
In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {...
1
vote
1
answer
112
views
Dataset of Hard Instances of SUBSET-SUM
I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-...
- 289
1
vote
1
answer
72
views
Converting a Mixed SUBSET-SUM Problem To All-Positive Case
Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent ...
- 289
0
votes
2
answers
65
views
Complexity of Subset Sum where the size of the subset is specified
I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.
Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a ...
- 1,601
0
votes
3
answers
159
views
Find the smallest group of numbers with sum bigger then $X$
Given a list of numbers $S$ where $0 < s_i < 100$, find the minimum sum group of numbers with a sum bigger than $X$.
Each number can be used multiple times.
Ex: for $S = [3,4.1], X = 10$ the ...
- 889
0
votes
1
answer
556
views
How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?
I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? ...
- 3
0
votes
0
answers
158
views
How to trace Subset from Boolean DP table in the Subset Sum Problem
I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result.
My questions are.
How did someone conclude that ...
- 101
2
votes
1
answer
91
views
How to prove the NP-completeness of MOD-PARTITION
MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
4
votes
1
answer
109
views
Enumerate all valid orders of subset sums
Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the ...
- 7,275
4
votes
1
answer
514
views
Two versions of Subset Sum Problem
I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:
Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
- 385
10
votes
2
answers
586
views
Subset sum problem for permutations
Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
- 103
2
votes
0
answers
37
views
Finding a non negative combination of integers that adds up to a certain number [duplicate]
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.
I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that
$$n_1c_1 + n_2c_2 + \dots + ...
3
votes
1
answer
45
views
Solve SUBSET SUM for Reciprocals of Primes
Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$.
Problem
Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
- 155
1
vote
1
answer
240
views
Return the subset with smallest cardinality of an array whose elements sum to at least a given value
Suppose we are given an array $A[1\ldots n]$ and a value $C$.
Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
- 43
2
votes
1
answer
77
views
complexity of a variant of the subset sum problem
We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.
What is the ...
- 385
2
votes
1
answer
131
views
find maximum sum of xors
we are given an Array
Array size <= 10^4 .
0 <= A[i] <= 15
We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
- 103
2
votes
2
answers
161
views
Minimizing the iterative sum of pairs of numbers in a list
Given the tuple (list, value):
$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$
You may choose two adjacent values in the list to modify the tuple as:
$$\left(\left[x_1, x_2, \cdots x_{i-1}, (...
- 123
1
vote
1
answer
74
views
Divide a number in k powers of 2
Example
N = 9 and K=3
4 + 4 + 1 = 9 .
What I have tried.
We can not go on dividing with 2.
We can use unbounded knapsack with array elements from 2^0 to 2^32.
- 103